Document Open Access Logo

On the Complexity Landscape of Connected f-Factor Problems

Authors Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak, C. S. Rahul, M. S. Ramanujan

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.41.pdf
  • Filesize: 0.74 MB
  • 14 pages

Document Identifiers

Author Details

Robert Ganian
N. S. Narayanaswamy
Sebastian Ordyniak
C. S. Rahul
M. S. Ramanujan

Cite As Get BibTex

Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak, C. S. Rahul, and M. S. Ramanujan. On the Complexity Landscape of Connected f-Factor Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.41

Abstract

Given an n-vertex graph G and a function f:V(G) -> {0, ..., n-1}, an f-factor is a subgraph H of G such that deg_H(v)=f(v) for every vertex v in V(G); we say that H is a connected f-factor if, in addition, the subgraph H is connected. A classical result of Tutte (1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connected f-factor is easily seen to generalize Hamiltonian Cycle and hence is NP-complete. In fact, the Connected f-Factor problem remains NP-complete even when f(v) is at least n^epsilon for each vertex v and epsilon<1; on the other side of the spectrum, the problem was known to be polynomial-time solvable when f(v) is at least n/3 for every vertex v. 

In this paper, we extend this line of work and obtain new complexity results based on restricting the function f. In particular, we show that when f(v) is required to be at least n/(log n)^c, the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c <= 1. We also show that when c>1, the problem is NP-intermediate.

Subject Classification

Keywords
  • f-factors
  • connected f-factors
  • quasi-polynomial time algorithms
  • randomized algorithms

Metrics

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

References

  1. Jin Akiyama and Mikio Kano. Factors and factorizations of graphs—a survey. Journal of Graph Theory, 9(1):1-42, 1985. Google Scholar
  2. F. Cheah and D. G. Corneil. The complexity of regular subgraph recognition. Discrete Applied Mathematics, 27(1-2):59-68, 1990. Google Scholar
  3. FRK Chung and RL Graham. Recent results in graph decompositions. London Mathematical Society, Lecture Note Series, 52:103-123, 1981. Google Scholar
  4. Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N.S. Narayanaswamy, and C.S. Rahul. Approximability of connected factors. In Christos Kaklamanis and Kirk Pruhs, editors, Approximation and Online Algorithms, volume 8447 of Lecture Notes in Computer Science, pages 120-131. Springer International Publishing, 2014. URL: http://dx.doi.org/10.1007/978-3-319-08001-7_11.
  5. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS, pages 150-159, 2011. Google Scholar
  6. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. Google Scholar
  7. Gregory Gutin, Magnus Wahlström, and Anders Yeo. Parameterized rural postman and conjoining bipartite matching problems. CoRR, abs/1308.2599, 2013. URL: http://arxiv.org/abs/1308.2599.
  8. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512 - 530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  9. Tomáš Kaiser. A short proof of the tree-packing theorem. Discrete Mathematics, 312(10):1689-1691, 2012. Google Scholar
  10. László Lovász. The factorization of graphs. ii. Acta Mathematica Academiae Scientiarum Hungarica, 23(1-2):223-246, 1972. Google Scholar
  11. László Lovász. On determinants, matchings, and random algorithms. In L. Budach, editor, Fundamentals of Computation Theory FCT '79, pages 565-574, Berlin, 1979. Akademie-Verlag. Google Scholar
  12. NS Narayanaswamy and CS Rahul. Approximation and exact algorithms for special cases of connected f-factors. In Computer Science-Theory and Applications, pages 350-363. Springer, 2015. Google Scholar
  13. Julius Petersen. Die theorie der regulären graphs. Acta Mathematica, 15(1):193-220, 1891. Google Scholar
  14. Geevarghese Philip and M. S. Ramanujan. Vertex exponential algorithms for connected f-factors. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India, pages 61-71, 2014. Google Scholar
  15. Geevarghese Philip and MS Ramanujan. Vertex exponential algorithms for connected f-factors. In LIPIcs-Leibniz International Proceedings in Informatics, volume 29. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  16. M. D. Plummer. Graph factors and factorization: 1985-2003: a survey. Discrete Mathematics, 307(7):791-821, 2007. Google Scholar
  17. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, October 1980. Google Scholar
  18. W. T. Tutte. A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics, 6(1954):347-352, 1954. URL: http://dx.doi.org/10.4153/CJM-1954-033-3.
  19. WT Tutte. The factors of graphs. Canad. J. Math, 4(3):314-328, 1952. Google Scholar
  20. Preben Dahl Vestergaard and Mekkia Kouider. Connected factors in graphs - a survey. Graphs and Combinatorics, 21(1):1-26, 2005. Google Scholar
  21. Magnus Wahlström. Abusing the tutte matrix: An algebraic instance compression for the k-set-cycle problem. In STACS, pages 341-352, 2013. Google Scholar
  22. D. B. West. Introduction to Graph Theory. Prentice Hall, 2001. Google Scholar
  23. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, volume 72, pages 216-226. 1979. 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