Output details

Fixed-parameter tractability of multicut parameterized by the size of the cutset

<12> We establish fixed-parameter tractability of the multicut problem, thus resolving a very challenging open question that has been tackled by many research groups in the last 5 years. An immediate consequence of our result is the fixed parameter tractability of the weighted correlation clustering problem, having direct applications in machine learning. The methodology behind the result is also of independent interest. Although the result is recent, there has been already a considerable follow up work by others applying our approach to the design of fixed-parameter algorithms for other challenging graph-theoretic problems. A journal version of this paper has been unconditionally accepted for publication in SIAM J. of Computing.