Document Open Access Logo

Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization

Authors Guilherme C. M. Gomes , Ignasi Sau

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2019.19.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Guilherme C. M. Gomes
  • Universidade Federal de Minas Gerais, Departamento de Ciência da Computação, Belo Horizonte, Brazil
  • LIRMM, Université de Montpellier, Montpellier, France
Ignasi Sau
  • CNRS, LIRMM, Université de Montpellier, Montpellier, France

Funding

  • C. M. Gomes, Guilherme: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001.
  • Sau, Ignasi: Projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).

Cite As Get BibTex

Guilherme C. M. Gomes and Ignasi Sau. Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2019.19

Abstract

A matching cut is a partition of the vertex set of a graph into two sets A and B such that each vertex has at most one neighbor in the other side of the cut. The Matching Cut problem asks whether a graph has a matching cut, and has been intensively studied in the literature. Motivated by a question posed by Komusiewicz et al. [IPEC 2018], we introduce a natural generalization of this problem, which we call d-Cut: for a positive integer d, a d-cut is a bipartition of the vertex set of a graph into two sets A and B such that each vertex has at most d neighbors across the cut. We generalize (and in some cases, improve) a number of results for the Matching Cut problem. Namely, we begin with an NP-hardness reduction for d-Cut on (2d+2)-regular graphs and a polynomial algorithm for graphs of maximum degree at most d+2. The degree bound in the hardness result is unlikely to be improved, as it would disprove a long-standing conjecture in the context of internal partitions. We then give FPT algorithms for several parameters: the maximum number of edges crossing the cut, treewidth, distance to cluster, and distance to co-cluster. In particular, the treewidth algorithm improves upon the running time of the best known algorithm for Matching Cut. Our main technical contribution, building on the techniques of Komusiewicz et al. [IPEC 2018], is a polynomial kernel for d-Cut for every positive integer d, parameterized by the distance to a cluster graph. We also rule out the existence of polynomial kernels when parameterizing simultaneously by the number of edges crossing the cut, the treewidth, and the maximum degree. Finally, we provide an exact exponential algorithm slightly faster than the naive brute force approach running in time O^*(2^n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Mathematics of computing → Matchings and factors
Keywords
  • matching cut
  • bounded degree cut
  • parameterized complexity
  • FPT algorithm
  • polynomial kernel
  • distance to cluster

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. N. R. Aravind, Subrahmanyam Kalyanasundaram, and Anjeneya Swami Kare. On Structural Parameterizations of the Matching Cut Problem. In Proc. of the 11th International Conference on Combinatorial Optimization and Applications (COCOA), volume 10628 of LNCS, pages 475-482, 2017. Google Scholar
  2. Amir Ban and Nati Linial. Internal partitions of regular graphs. Journal of Graph Theory, 83(1):5-18, 2016. Google Scholar
  3. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. Journal of Computer and System Sciences, 75(8):423-434, 2009. Google Scholar
  4. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Cross-Composition: A New Technique for Kernelization Lower Bounds. In Proc. of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 9 of LIPIcs, pages 165-176, 2011. Google Scholar
  5. Paul S. Bonsma. The complexity of the matching-cut problem for planar graphs and other graph classes. Journal of Graph Theory, 62(2):109-126, 2009. Google Scholar
  6. Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk. A fast branching algorithm for cluster vertex deletion. Theory of Computing Systems, 58(2):357-376, 2016. Google Scholar
  7. Vasek Chvátal. Recognizing decomposable graphs. Journal of Graph Theory, 8(1):51-53, 1984. Google Scholar
  8. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation, 85(1):12-75, 1990. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  10. Matt DeVos. http://www.openproblemgarden.org/op/friendly_partitions, 2009. Google Scholar
  11. Reinhard Diestel. Graph Theory, volume 173. Springer-Verlag, 4th edition, 2010. Google Scholar
  12. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  13. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. Google Scholar
  14. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences, 77(1):91-106, 2011. Google Scholar
  15. Ron L Graham. On primitive graphs and optimal vertex assignments. Annals of the New York academy of sciences, 175(1):170-186, 1970. Google Scholar
  16. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  17. Atsushi Kaneko. On decomposition of triangle-free graphs under degree constraints. Journal of Graph Theory, 27(1):7-9, 1998. Google Scholar
  18. Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms. In Proc. of the 13th International Symposium on Parameterized and Exact Computation (IPEC), volume 115 of LIPIcs, pages 19:1-19:13, 2018. Google Scholar
  19. Dieter Kratsch and Van Bang Le. Algorithms solving the matching cut problem. Theoretical Computer Science, 609:328-335, 2016. Google Scholar
  20. Hoàng-Oanh Le and Van Bang Le. On the Complexity of Matching Cut in Graphs of Fixed Diameter. In Proc. of the 27th International Symposium on Algorithms and Computation (ISAAC), volume 64 of LIPIcs, pages 50:1-50:12, 2016. Google Scholar
  21. Van Bang Le and Bert Randerath. On stable cutsets in line graphs. Theoretical Computer Science, 301(1-3):463-475, 2003. Google Scholar
  22. Jie Ma and Tianchi Yang. Decomposing C₄-free graphs under degree constraints. Journal of Graph Theory, 90(1):13-23, 2019. Google Scholar
  23. Dániel Marx, Barry O'Sullivan, and Igor Razgon. Treewidth Reduction for Constrained Separation and Bipartization Problems. In Proc. of the 27th International Symposium on Theoretical Aspects of Computer Science, (STACS), volume 5 of LIPIcs, pages 561-572, 2010. Google Scholar
  24. Augustine M Moshi. Matching cutsets in graphs. Journal of Graph Theory, 13(5):527-536, 1989. Google Scholar
  25. Maurizio Patrignani and Maurizio Pizzonia. The complexity of the matching-cut problem. In Proc. of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 2204 of LNCS, pages 284-295, 2001. Google Scholar
  26. Khurram H. Shafique and Ronald D. Dutton. On satisfactory partitioning of graphs. Congressus Numerantium, pages 183-194, 2002. Google Scholar
  27. Michael Stiebitz. Decomposing graphs under degree constraints. Journal of Graph Theory, 23(3):321-324, 1996. Google Scholar
  28. Carsten Thomassen. Graph decomposition with constraints on the connectivity and minimum degree. Journal of Graph Theory, 7(2):165-167, 1983. Google Scholar
  29. Chee-Keng Yap. Some Consequences of Non-Uniform Conditions on Uniform Classes. Theoretical Computer Science, 26:287-300, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact