Treewidth reduction for constrained separation and bipartization problems

Details Treewidth reduction for constrained separation and bipartization problems Treewidth reduction for constrained separation and bipartization problems

2009-02-22

arxiv.org/abs/0902.3780v3

Computer Science

Data Structures and Algorithms

STACS final version of our result. For the complete description of the result please see version 1

Scientific paper

We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These results answer a number of open questions in the area of parameterized complexity.

Affiliated with

Also associated with

No associations

Rating

Treewidth reduction for constrained separation and bipartization problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Treewidth reduction for constrained separation and bipartization problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Treewidth reduction for constrained separation and bipartization problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-99184