LIPIcs.ICALP.2018.112.pdf
- Filesize: 397 kB
- 6 pages
Document
Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable
Authors
Mingyu Xiao 
,
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
File
Document Identifiers
Author Details
Cite AsGet BibTex
Mingyu Xiao and Hiroshi Nagamochi. Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 112:1-112:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.112
https://doi.org/10.4230/LIPIcs.ICALP.2018.112
Abstract
In the bounded-degree cut problem, we are given a multigraph G=(V,E), two disjoint vertex subsets A,B subseteq V, two functions u_A, u_B:V -> {0,1,...,|E|} on V, and an integer k >= 0. The task is to determine whether there is a minimal (A,B)-cut (V_A,V_B) of size at most k such that the degree of each vertex v in V_A in the induced subgraph G[V_A] is at most u_A(v) and the degree of each vertex v in V_B in the induced subgraph G[V_B] is at most u_B(v). In this paper, we show that the bounded-degree cut problem is fixed-parameter tractable by giving a 2^{18k}|G|^{O(1)}-time algorithm. This is the first single exponential FPT algorithm for this problem. The core of the algorithm lies two new lemmas based on important cuts, which give some upper bounds on the number of candidates for vertex subsets in one part of a minimal cut satisfying some properties. These lemmas can be used to design fixed-parameter tractable algorithms for more related problems.
Subject Classification
ACM Subject Classification
- Theory of computation → Fixed parameter tractability
- Mathematics of computing → Graph algorithms
Keywords
- FPT
- Important Cuts
- Graph Cuts
- Graph Algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and graph partitioning. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 222-231. ACM, 2004. URL: http://dx.doi.org/10.1145/1007352.1007355.
- Jørgen Bang-Jensen and Stéphane Bessy. Degree-constrained 2-partitions of graphs. CoRR, abs/1801.06216, 2018. URL: http://arxiv.org/abs/1801.06216.
- Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. Degree-constrained decompositions of graphs: Bounded treewidth and planarity. Theor. Comput. Sci., 355(3):389-395, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.01.024.
- Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. Efficient algorithms for decomposing graphs under degree constraints. Discrete Applied Mathematics, 155(8):979-988, 2007. URL: http://dx.doi.org/10.1016/j.dam.2006.10.005.
- Gruia Călinescu, Cristina G. Fernandes, and Bruce A. Reed. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. J. Algorithms, 48(2):333-359, 2003. URL: http://dx.doi.org/10.1016/S0196-6774(03)00073-7.
- Jianer Chen, Yang Liu, and Songjian Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 55(1):1-13, 2009. URL: http://dx.doi.org/10.1007/s00453-007-9130-6.
- Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Minimum bisection is fixed parameter tractable. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 323-332. ACM, 2014. URL: http://dl.acm.org/citation.cfm?id=2591796, URL: http://dx.doi.org/10.1145/2591796.2591852.
- Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Solving the 2-disjoint connected subgraphs problem faster than 2 n. Algorithmica, 70(2):195-207, 2014. URL: http://dx.doi.org/10.1007/s00453-013-9796-x.
- Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. The complexity of multiterminal cuts. SIAM J. Comput., 23(4):864-894, 1994. URL: http://dx.doi.org/10.1137/S0097539792225297.
- Uriel Feige and Robert Krauthgamer. A polylogarithmic approximation of the minimum bisection. SIAM J. Comput., 31(4):1090-1118, 2002. URL: http://dx.doi.org/10.1137/S0097539701387660.
- Uriel Feige, Robert Krauthgamer, and Kobbi Nissim. Approximating the minimum bisection size (extended abstract). In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 530-536. ACM, 2000. URL: http://dx.doi.org/10.1145/335305.335370.
- Uriel Feige and Mohammad Mahdian. Finding small balanced separators. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 375-384. ACM, 2006. URL: http://dx.doi.org/10.1145/1132516.1132573.
-
L.R. Ford and Delbert R. Fulkerson. Flows in networks. Princeton U. Press, Princeton, NJ, 1962.
- Olivier Goldschmidt and Dorit S. Hochbaum. A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res., 19(1):24-37, 1994. URL: http://dx.doi.org/10.1287/moor.19.1.24.
- Ken-ichi Kawarabayashi and Mikkel Thorup. The minimum k-way cut of bounded size is fixed-parameter tractable. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 160-169. IEEE Computer Society, 2011. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120, URL: http://dx.doi.org/10.1109/FOCS.2011.53.
- Frank Thomson Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787-832, 1999. URL: http://dx.doi.org/10.1145/331524.331526.
- Daniel Lokshtanov, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Balanced judicious bipartition is fixed-parameter tractable. In Satya V. Lokam and R. Ramanujam, editors, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India, volume 93 of LIPIcs, pages 40:40-40:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://www.dagstuhl.de/dagpub/978-3-95977-055-2, URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.40.
- Dániel Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394-406, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2005.10.007.
- Dániel Marx and Igor Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 469-478. ACM, 2011. URL: http://dx.doi.org/10.1145/1993636.1993699.
- Michael Stiebitz. Decomposing graphs under degree constraints. Journal of Graph Theory, 23(3):321-324, 1996. URL: http://dx.doi.org/10.1002/(SICI)1097-0118(199611)23:3<321::AID-JGT12>3.0.CO;2-H.
- Mingyu Xiao. Simple and improved parameterized algorithms for multiterminal cuts. Theory Comput. Syst., 46(4):723-736, 2010. URL: http://dx.doi.org/10.1007/s00224-009-9215-5.
- Mingyu Xiao and Hiroshi Nagamochi. Complexity and kernels for bipartition into degree-bounded induced graphs. Theor. Comput. Sci., 659:72-82, 2017. URL: http://dx.doi.org/10.1016/j.tcs.2016.11.011.