Large Isolating Cuts Shrink the Multiway Cut

Details Large Isolating Cuts Shrink the Multiway Cut Large Isolating Cuts Shrink the Multiway Cut

2011-04-28

arxiv.org/abs/1104.5361v2

Computer Science

Discrete Mathematics

Marcin Piliczuk has communicated to me a negative answer to the first open question. The graph was designed for a different pu

Scientific paper

We propose a preprocessing algorithm for the multiway cut problem that establishes its polynomial kernelizability when the difference between the parameter $k$ and the size of the smallest isolating cut is at most $log(k)$. To the best of our knowledge, this is the first progress towards kernelization of the multiway cut problem. We pose two open questions that, if answered affirmatively, would imply, combined with the proposed result, unconditional polynomial kernelizability of the multiway cut problem.

Affiliated with

Also associated with

No associations

Rating

Large Isolating Cuts Shrink the Multiway Cut 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 Large Isolating Cuts Shrink the Multiway Cut, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large Isolating Cuts Shrink the Multiway Cut will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-449567