Document Open Access Logo

The Complexity of Finding S-Factors in Regular Graphs

Authors Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2019.21.pdf
  • Filesize: 488 kB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Matchings and factors
  • Theory of computation → Problems, reductions and completeness
Keywords
  • constraint satisfaction problem
  • Dichotomy theorem
  • Graph Factors
  • Regular Graphs

Metrics

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

Abstract

A graph G has an S-factor if there exists a spanning subgraph F of G such that for all v in V: deg_F(v) in S. The simplest example of such factor is a 1-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational complexity of finding S-factors in regular graphs. Our techniques combine some classical as well as recent tools from graph theory.

Cite As Get BibTex

Sanjana Kolisetty, Linh Le, Ilya Volkovich, and Mihalis Yannakakis. The Complexity of Finding S-Factors in Regular Graphs. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.FSTTCS.2019.21

Author Details

Sanjana Kolisetty
  • Departments of Mathematics and EECS, CSE Division, University of Michigan, Ann Arbor, MI, USA
Linh Le
  • Departments of Mathematics and EECS, CSE Division, University of Michigan, Ann Arbor, MI, USA
Ilya Volkovich
  • Department of EECS, CSE Division, University of Michigan, Ann Arbor, MI, USA
Mihalis Yannakakis
  • Department of Computer Science, Columbia University, New York, NY, USA

Funding

Research partially supported by the NSF-CCF AitF 1535912 Grant.
  • Kolisetty, Sanjana: Research partially supported by the NSF-CCF AitF 1535912 Grant.
  • Le, Linh: Research partially supported by the NSF-CCF AitF 1535912 Grant.

Acknowledgements

The authors would like to thank the anonymous referees for their detailed comments and suggestions on the previous version of the paper.

References

  1. S. Akbari and M. Kano. k, r - k-Factors of r-Regular Graphs. Graphs and Combinatorics, 30(4):821-826, 2014. URL: https://doi.org/10.1007/s00373-013-1324-x.
  2. J. Akiyama and M. Kano. Factors and factorizations of graphs - a survey. Journal of Graph Theory, 9(1):1-42, 1985. URL: https://doi.org/10.1002/jgt.3190090103.
  3. E. Allender, M. Bauland, N. Immerman, H. Schnoor, and H. Vollmer. The complexity of satisfiability problems: Refining Schaefer’s theorem. J. Comput. Syst. Sci., 75(4):245-254, 2009. URL: https://doi.org/10.1016/j.jcss.2008.11.001.
  4. C. Berge. Graphs and Hypergraphs. North-Holland mathematical library. Amsterdam, 1973. Google Scholar
  5. A. Bernshteyn, O. Khormali, R. R. Martin, J. Rollin, D. Rorabaugh, S. Shan, and A. J. Uzzell. Regular colorings and factors of regular graphs. CoRR, abs/1603.09384, 2016. URL: http://arxiv.org/abs/1603.09384.
  6. A. A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 319-330, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  7. V. Dalmau and D. K. Ford. Generalized Satisfability with Limited Occurrences per Variable: A Study through Delta-Matroid Parity. In The 28th International Symposium Mathematical Foundations of Computer Science MFCS, pages 358-367, 2003. URL: https://doi.org/10.1007/978-3-540-45138-9_30.
  8. Z. Dvorak and M. Kupec. On Planar Boolean CSP. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 432-443, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_35.
  9. J. Edmonds. Paths, Trees and Flowers. CANADIAN JOURNAL OF MATHEMATICS, pages 449-467, 1965. Google Scholar
  10. T. Feder. Fanout limitations on constraint systems. Theor. Comput. Sci., 255(1-2):281-293, 2001. URL: https://doi.org/10.1016/S0304-3975(99)00288-1.
  11. T. Feder and D. K. Ford. Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection. SIAM J. Discrete Math., 20(2):372-394, 2006. URL: https://doi.org/10.1137/S0895480104445009.
  12. T. Feder and M. Y. Vardi. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM J. Comput., 28(1):57-104, 1998. URL: https://doi.org/10.1137/S0097539794266766.
  13. T. Gallai. On factorisation of graphs. Acta Mathematica Academiae Scientiarum Hungarica, 1(1):133-153, March 1950. URL: https://doi.org/10.1007/BF02022560.
  14. J. F. Geelen, S. Iwata, and K. Murota. The linear delta-matroid parity problem. J. Comb. Theory, Ser. B, 88(2):377-398, 2003. URL: https://doi.org/10.1016/S0095-8956(03)00039-X.
  15. G. Istrate. Looking for a Version of Schaefer"s Dichotomy Theorem When Each Variable Occurs at Most Twice. Technical report, University of Rochester, Rochester, NY, USA, 1997. Google Scholar
  16. M. Kano and H. Matsuda. Partial Parity (g, f)-Factors and Subgraphs Covering Given Vertex Subsets. Graphs and Combinatorics, 17(3):501-509, 2001. URL: https://doi.org/10.1007/PL00013412.
  17. A. Kazda, V. Kolmogorov, and M. Rolínek. Even Delta-Matroids and the Complexity of Planar Boolean CSPs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 307-326, 2017. URL: https://doi.org/10.1137/1.9781611974782.20.
  18. L. Lovász. The factorization of graphs. II. Acta Mathematica Academiae Scientiarum Hungarica, 23(1):223-246, March 1972. URL: https://doi.org/10.1007/BF01889919.
  19. H. Lu, D. G. L. Wang, and Q. Yu. On the Existence of General Factors in Regular Graphs. SIAM J. Discrete Math., 27(4):1862-1869, 2013. URL: https://doi.org/10.1137/120895792.
  20. URL: https://doi.org/10.1007/BF02392606.
  21. M. D. Plummer. Graph factors and factorization: 1985-2003: A survey. Discrete Mathematics, 307(7-8):791-821, 2007. Google Scholar
  22. T. J. Schaefer. The Complexity of Satisfiability Problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 216-226, 1978. URL: https://doi.org/10.1145/800133.804350.
  23. W.T. Tutte. The Subgraph Problem. In Advances in Graph Theory, volume 3 of Annals of Discrete Mathematics, pages 289-295. Elsevier, 1978. URL: https://doi.org/10.1016/S0167-5060(08)70514-4.
  24. D. Zhuk. A Proof of CSP Dichotomy Conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 331-342, 2017. URL: https://doi.org/10.1109/FOCS.2017.38.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact