research-article

On multiway cut parameterized above lower bounds

Authors:

Marcin Pilipczuk,

Michał Pilipczuk,

Jakub Onufry WojtaszczykAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 5, Issue 1

Article No.: 3, Pages 1 - 11

https://doi.org/10.1145/2462896.2462899

Published: 29 May 2013 Publication History

Abstract

We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the node multiway cut problem is fixed-parameter tractable (FPT) in this setting. As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon.

Our results imply O^*(4^k) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an O^*(2^k) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.

References

[1]

Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé. 2011. Multicut is FPT. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11). ACM, New York, 459--468.

Digital Library

[2]

Jianer Chen, Yang Liu, and Songjian Lu. 2009. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55, 1, 1--13.

Digital Library

[3]

Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. 2008. A fixed-parameter algorithm for the directed feedback vertex set problem. In Proceedings of the ACM Symposium on Theory of Computing (STOC'08). ACM, New York, 177--186.

Digital Library

[4]

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. 2011. On multiway cut parameterized above lower bounds. In Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC'11). 1--12.

Digital Library

[5]

Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. 1994. The complexity of multiterminal cuts. SIAM J. Comput. 23, 4, 864--894.

Digital Library

[6]

Rodney G. Downey and Michael R. Fellows. 1999. Parameterized complexity. Springer, Berlin. citeseer.ist.psu.edu/downey98parameterized.html.

Digital Library

[7]

Micheal R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. 2009. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410, 53--61.

Digital Library

[8]

Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory 1st Ed. Springer, Berlin. http://www.worldcat.org/isbn/3540299521.

Digital Library

[9]

Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. 2004. Multiway cuts in node weighted graphs. J. Algor. 50, 1, 49--61.

Digital Library

[10]

Sylvain Guillemot. 2011. FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optim. 8, 1, 61--71.

Digital Library

[11]

Gregory Gutin, Eun Jung Kim, Michael Lampis, and Valia Mitsou. 2011. Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst. 48, 2. 402--410.

Digital Library

[12]

Gregory Gutin, Leo van Iersel, Matthias Mnich, and Anders Yeo. 2010. All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables. In Proceedings of the International Conference on Embedded Systems and Applications (ESA'10). 326--337.

Digital Library

[13]

Meena Mahajan and Venkatesh Raman. 1999. Parameterizing above guaranteed values: MaxSat and Max-Cut. J. Algor. 31, 2, 335--354.

Digital Library

[14]

Daniel Marx. 2006. Parameterized graph separation problems. Theor. Comput. Sci. 351, 3, 394--406.

Digital Library

[15]

Daniel Marx and Igor Razgon. 2011. Fixed-parameter tractability of multicut parameterized by the size of the cutset. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11). ACM, New York, 469--478.

Digital Library

[16]

N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. 2012. LP can be a cure for Parameterized Problems. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS'12). 338--349.

[17]

Rolf Niedermeier. 2006. Invitation to Fixed Parameter Algorithms. Oxford University Press. http://www.worldcat.org/isbn/0198566077.

[18]

Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. 2011. Paths, flowers and vertex cover. In Proceedings of the European Symposium on Algorithms (ESA'11). 382--393.

Digital Library

[19]

Igor Razgon. 2010. Computing multiway cut within the given excess over the largest minimum isolating cut. CoRR abs/1011.6267 (2010).

[20]

Igor Razgon. 2011. Large isolating cuts shrink the multiway cut. CoRR abs/1104.5361 (2011).

[21]

Igor Razgon and Barry O'Sullivan. 2009. Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75, 8, 435--450.

Digital Library

[22]

Mingyu Xiao. 2010. Simple and improved parameterized algorithms for multiterminal cuts. Theory Comput. Syst. 46, 4, 723--736.

Digital Library

Cited By

Jansen Bde Kroon JWłodarczyk M(2025)Single-exponential FPT algorithms for enumerating secluded F-free subgraphs and deleting to scattered graph classesJournal of Computer and System Sciences10.1016/j.jcss.2024.103597148:COnline publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1016/j.jcss.2024.103597
Peng JXiao MLarson K(2024)A fast algorithm for MaxSAT above half number of clausesProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/214(1935-1943)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/214
Kim EMasařík TPilipczuk MSharma RWahlström M(2024)On Weighted Graph Separation Problems and Flow AugmentationSIAM Journal on Discrete Mathematics10.1137/22M153118X38:1(170-189)Online publication date: 8-Jan-2024
https://doi.org/10.1137/22M153118X
Show More Cited By

Index Terms

On multiway cut parameterized above lower bounds
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset

Given a directed graph $G$, a set of $k$ terminals, and an integer $p$, the Directed Vertex Multiway Cut problem asks whether there is a set $S$ of at most $p$ (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed ...
Parameterised Algorithms for Deletion to Classes of DAGs

In the Directed Feedback Vertex Set (DFVS) problem, we are given a digraph D on n vertices and a positive integer k, and the objective is to check whether there exists a set of vertices S such that F = D ? S is an acyclic digraph. In a recent paper, ...
On parameterized exponential time complexity

In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2^o^(^f^(^k^)^)p(n) time if and only if it is solvable in time O(2^@d^f^(^k^)q(n)) for any constant @d>0, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 5, Issue 1

May 2013

58 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/2462896

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 May 2013

Accepted: 01 January 2013

Received: 01 February 2012

Revised: 01 November 2011

Published in TOCT Volume 5, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
379
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)5

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jansen Bde Kroon JWłodarczyk M(2025)Single-exponential FPT algorithms for enumerating secluded F-free subgraphs and deleting to scattered graph classesJournal of Computer and System Sciences10.1016/j.jcss.2024.103597148:COnline publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1016/j.jcss.2024.103597
Peng JXiao MLarson K(2024)A fast algorithm for MaxSAT above half number of clausesProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/214(1935-1943)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/214
Kim EMasařík TPilipczuk MSharma RWahlström M(2024)On Weighted Graph Separation Problems and Flow AugmentationSIAM Journal on Discrete Mathematics10.1137/22M153118X38:1(170-189)Online publication date: 8-Jan-2024
https://doi.org/10.1137/22M153118X
Jacob AWłodarczyk MZehavi M(2024)Long directed detours: Reduction to 2-Disjoint PathsInformation Processing Letters10.1016/j.ipl.2024.106491186(106491)Online publication date: Aug-2024
https://doi.org/10.1016/j.ipl.2024.106491
Li SPilipczuk MSorge M(2023)Cluster Editing Parameterized above Modification-disjoint P3-packingsACM Transactions on Algorithms10.1145/362652620:1(1-43)Online publication date: 11-Oct-2023
https://dl.acm.org/doi/10.1145/3626526
Bentert Mvan Bevern RNichterlein ANiedermeier RSmirnov P(2022)Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor NetworksINFORMS Journal on Computing10.1287/ijoc.2020.104534:1(55-75)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1287/ijoc.2020.1045
Jacob APanolan FRaman VSahlot V(2022)Structural Parameterizations with Modulator OblivionAlgorithmica10.1007/s00453-022-00971-784:8(2335-2357)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s00453-022-00971-7
Bergougnoux BPapadopoulos CTelle J(2022)Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-WidthAlgorithmica10.1007/s00453-022-00936-w84:5(1385-1417)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s00453-022-00936-w
Kim EKratsch SPilipczuk MWahlström MMarx D(2021)Solving hard cut problems via flow-augmentationProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458075(149-168)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458075
Jansen BPilipczuk Mvan Leeuwen E(2021)A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar GraphsSIAM Journal on Discrete Mathematics10.1137/20M135378235:4(2387-2429)Online publication date: 18-Oct-2021
https://doi.org/10.1137/20M1353782
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents