Document Open Access Logo

Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes

Authors Radu Curticapean, Holger Dell, Marc Roth

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.25.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Radu Curticapean
Holger Dell
Marc Roth

Cite As Get BibTex

Radu Curticapean, Holger Dell, and Marc Roth. Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.25

Abstract

We consider the parameterized problem of counting all matchings with exactly k edges in a given input graph G. This problem is #W[1]-hard (Curticapean, ICALP 2013), so it is unlikely to admit f(k)poly(n) time algorithms. We show that #W[1]-hardness persists even when the input graph G comes from restricted graph classes, such as line graphs and bipartite graphs of arbitrary constant girth and maximum degree two on one side.

To prove the result for line graphs, we observe that k-matchings in line graphs can be equivalently viewed as edge-injective homomorphisms from the disjoint union of k paths of length two into (arbitrary) host graphs. Here, a homomorphism from H to G is edge-injective if it maps any two distinct edges of H to distinct edges in G. We show that edge-injective homomorphisms from a pattern graph H can be counted in polynomial time if H has bounded vertex-cover number after removing isolated edges. For hereditary classes H of pattern graphs, we obtain a full complexity dichotomy theorem by proving that counting edge-injective homomorphisms, restricted to patterns from H, is #W[1]-hard if no such bound exists.

Our proofs rely on an edge-colored variant of Holant problems and a delicate interpolation argument; both may be of independent interest.

Subject Classification

Keywords
  • matchings
  • homomorphisms
  • line graphs
  • counting complexity
  • parameterized complexity

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. URL: http://dx.doi.org/10.1145/210332.210337.
  2. Jin-Yi Cai and Zhiguo Fu. Holographic algorithm with matchgates is universal for planar #CSP over boolean domain. CoRR, abs/1603.07046, 2016. URL: http://arxiv.org/abs/1603.07046.
  3. Jin-Yi Cai and Lane A. Hemachandra. On the power of parity polynomial time. Mathematical Systems Theory, 23(2):95-106, 1990. URL: http://dx.doi.org/10.1007/BF02090768.
  4. Jin-Yi Cai and Pinyan Lu. Holographic algorithms: From art to science. In Proceedings of the 39th ACM Symposium on Theory of Computing, STOC, pages 401-410, 2007. URL: http://dx.doi.org/10.1145/1250790.1250850.
  5. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holographic algorithms by Fibonacci gates and holographic reductions for hardness. In Proc. of the 49th Annual Symposium on Foundations of Computer Science, FOCS, pages 644-653, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.34.
  6. Jin-yi Cai, Pinyan Lu, and Mingji Xia. Holographic algorithms with matchgates capture precisely tractable planar #CSP. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 427-436, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.48.
  7. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of holant problems. SIAM Journal on Computing, 40(4):1101-1132, 2011. URL: http://dx.doi.org/10.1137/100814585.
  8. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. Information and Computation, 201(2):216-231, 2005. URL: http://dx.doi.org/10.1016/j.ic.2005.05.001.
  9. Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the complexity of induced subgraph isomorphisms. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP, pages 587-596, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70575-8_48.
  10. Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Annals of mathematics, pages 51-229, 2006. Google Scholar
  11. Radu Curticapean. Counting matchings of size k is #W[1]-hard. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP, pages 352-363, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_30.
  12. Radu Curticapean. The simple, little and slow things count: On parameterized counting complexity. PhD thesis, Saarland University, August 2015. Google Scholar
  13. Radu Curticapean and Dániel Marx. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In Proceedings of the 55th Annual Symposium on Foundations of Computer Science, FOCS, pages 130-139. IEEE, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.22.
  14. Radu Curticapean and Mingji Xia. Parameterizing the permanent: Genus, apices, minors, evaluation mod 2^k. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science, FOCS, pages 994-1009, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.65.
  15. Paul Dagum and Michael Luby. Approximating the permanent of graphs with large factors. Theoretical Computer Science, 102(2):283-305, 1992. URL: http://dx.doi.org/10.1016/0304-3975(92)90234-7.
  16. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science, 329(1-3):315-323, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2004.08.008.
  17. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. Exponential time complexity of the permanent and the Tutte polynomial. ACM Transactions on Algorithms, 10(4):21, 2014. URL: http://dx.doi.org/10.1145/2635812.
  18. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM Journal of Computing, 33(4):892-922, 2004. URL: http://dx.doi.org/10.1137/S0097539703427203.
  19. Jörg Flum and Martin Grohe. Parameterized complexity theory. Springer, 2006. Google Scholar
  20. Markus Frick. Generalized model-checking over locally tree-decomposable classes. Theoretical Computer Science, 37(1):157-191, 2004. URL: http://dx.doi.org/10.1007/s00224-003-1111-9.
  21. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1):1, 2007. URL: http://dx.doi.org/10.1145/1206035.1206036.
  22. Martin Grohe, Thomas Schwentick, and Luc Segoufin. When is the evaluation of conjunctive queries tractable? In Proceedings of the 33rd ACM Symposium on Theory of Computing, STOC, pages 657-666, 2001. URL: http://dx.doi.org/10.1145/380752.380867.
  23. Venkatesan Guruswami. Maximum cut on line and total graphs. Discrete Applied Mathematics, 92(2-3):217-221, 1999. URL: http://dx.doi.org/10.1016/S0166-218X(99)00056-6.
  24. Frank Harary. Graph theory, 1969. Google Scholar
  25. Mark Jerrum. Two-dimensional monomer-dimer systems are computationally intractable. Journal of Statistical Physics, 48(1-2):121-134, 1987. URL: http://dx.doi.org/10.1007/BF01010403.
  26. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM, 51(4):671-697, 2004. URL: http://dx.doi.org/10.1145/1008731.1008738.
  27. Pieter W. Kasteleyn. Graph theory and crystal physics. In Graph Theory and Theoretical Physics, pages 43-110. Academic Press, 1967. Google Scholar
  28. Philippe G. H. Lehot. An optimal algorithm to detect a line graph and output its root graph. Journal of the ACM, 21(4):569-575, 1974. URL: http://dx.doi.org/10.1145/321850.321853.
  29. Bingkai Lin. The parameterized complexity of k-biclique. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 605-615, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.41.
  30. Vadim V. Lozin and Raffaele Mosca. Independent sets in extensions of 2K₂-free graphs. Discrete Applied Mathematics, 146(1):74-80, 2005. URL: http://dx.doi.org/10.1016/j.dam.2004.07.006.
  31. Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Applied Mathematics, 198:170-194, 2016. URL: http://dx.doi.org/10.1016/j.dam.2015.06.019.
  32. Najiba Sbihi. Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile. Discrete Mathematics, 29:53-76, 1980. URL: http://dx.doi.org/10.1016/0012-365X(90)90287-R.
  33. Harold N. V. Temperley and Michael E. Fisher. Dimer problem in statistical mechanics - an exact result. Philosophical Magazine, 6(68):1478-6435, 1961. Google Scholar
  34. Salil P. Vadhan. The complexity of counting in sparse, regular, and planar graphs. SIAM Journal of Computing, 31(2):398-427, 2001. URL: http://dx.doi.org/10.1137/S0097539797321602.
  35. Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-201, 1979. Google Scholar
  36. Leslie G. Valiant. Holographic algorithms. SIAM Journal of Computing, 37(5):1565-1594, 2008. URL: http://dx.doi.org/10.1137/070682575.
  37. Ľ. Šoltés. Forbidden induced subgraphs for line graphs. Discrete Mathematics, 132(1):391-394, 1994. Google Scholar
  38. Mingji Xia, Peng Zhang, and Wenbo Zhao. Computational complexity of counting problems on 3-regular planar graphs. Theoretical Computer Science, 384(1):111-125, 2007. Theory and Applications of Models of Computation. URL: http://dx.doi.org/10.1016/j.tcs.2007.05.023.
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