Minimum k-way cut of bounded size is fixed-parameter tractable

Details Minimum k-way cut of bounded size is fixed-parameter tractable Minimum k-way cut of bounded size is fixed-parameter tractable

2011-01-24

arxiv.org/abs/1101.4689v2

Computer Science

Discrete Mathematics

Scientific paper

We consider a the minimum k-way cut problem for unweighted graphs with a size bound s on the number of cut edges allowed. Thus we seek to remove as few edges as possible so as to split a graph into k components, or report that this requires cutting more than s edges. We show that this problem is fixed-parameter tractable (FPT) in s. More precisely, for s=O(1), our algorithm runs in quadratic time while we have a different linear time algorithm for planar graphs and bounded genus graphs. Our tractability result stands in contrast to known W[1] hardness of related problems. Without the size bound, Downey et al.[2003] proved that the minimum k-way cut problem is W[1] hard in k even for simple unweighted graphs. Downey et al. asked about the status for planar graphs. Our result implies tractability in k for the planar graphs since the minimum k-way cut of a planar graph is of size at most 6k (more generally, we get tractability in k for any graph class with k-way cuts of size limited by is a function of k, e.g., bounded degree graphs, or simple graphs with an excluded minor). A simple reduction shows that vertex cuts are at least as hard as edge cuts, so the minimum k-way vertex cut is also W[1] hard in terms of k. Marx [2004] proved that finding a minimum k-way vertex cut of size s is also W[1] hard in s. Marx asked about the FPT status with edge cuts, which we prove tractable here. We are not aware of any other cut problem where the vertex version is W[1] hard but the edge version is FPT.

Affiliated with

Also associated with

No associations

Rating

Minimum k-way cut of bounded size is fixed-parameter tractable 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 Minimum k-way cut of bounded size is fixed-parameter tractable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum k-way cut of bounded size is fixed-parameter tractable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-541334