Document Open Access Logo

Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices

Author Marc Roth

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.63.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Marc Roth

Cite As Get BibTex

Marc Roth. Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.63

Abstract

We present a framework for the complexity classification of parameterized counting problems that can be formulated as the summation over the numbers of homomorphisms from small pattern graphs H_1,...,H_l to a big host graph G with the restriction that the coefficients correspond to evaluations of the Möbius function over the lattice of a graphic matroid. This generalizes the idea of Curticapean, Dell and Marx [STOC 17] who used a result of Lovász stating that the number of subgraph embeddings from a graph H to a graph G can be expressed as such a sum over the lattice of partitions of H. In the first step we introduce what we call graphically restricted homomorphisms that, inter alia, generalize subgraph embeddings as well as locally injective homomorphisms. We provide a complete parameterized complexity dichotomy for counting such homomorphisms, that is, we identify classes of patterns for which the problem is fixed-parameter tractable (FPT), including an algorithm, and prove that all other pattern classes lead to #W[1]-hard problems. The main ingredients of the proof are the complexity classification of linear combinations of homomorphisms due to Curticapean, Dell and Marx [STOC 17] as well as a corollary of Rota's NBC Theorem which states that the sign of the Möbius function over a geometric lattice only depends on the rank of its arguments. We apply the general theorem to the problem of counting locally injective homomorphisms from small pattern graphs to big host graphs yielding a concrete dichotomy criterion. It turns out that - in contrast to subgraph embeddings - counting locally injective homomorphisms has "real" FPT cases, that is, cases that are fixed-parameter tractable but not polynomial time solvable under standard complexity assumptions. To prove this we show in an intermediate step that the subgraph counting problem remains #P-hard when both the pattern and the host graphs are restricted to be trees. We then investigate the more general problem of counting homomorphisms that are injective in the r-neighborhood of every vertex. As those are graphically restricted as well, they can also easily be classified via the general theorem. Finally we show that the dichotomy for counting graphically restricted homomorphisms readily extends to so-called linear combinations.

Subject Classification

Keywords
  • homomorphisms
  • matroids
  • counting complexity
  • parameterized complexity
  • dichotomy theorems

Metrics

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

References

  1. Andreas Blass and Bruce E. Sagan. Möbius functions of lattices. Advances in mathematics, 127(1):94-123, 1997. Google Scholar
  2. Graham R. Brightwell and Peter Winkler. Note on counting eulerian circuits. CoRR, cs.CC/0405067, 2004. URL: http://arxiv.org/abs/cs.CC/0405067.
  3. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. CoRR, abs/1703.03021, 2017. URL: http://arxiv.org/abs/1703.03021.
  4. Jin-yi Cai, Pinyan Lu, and Mingji Xia. Holographic algorithms by fibonacci gates and holographic reductions for hardness. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 644-653, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.34.
  5. Jin-yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of holant problems. SIAM J. Comput., 40(4):1101-1132, 2011. URL: http://dx.doi.org/10.1137/100814585.
  6. Radu Curticapean. Counting matchings of size k is #W[1]-hard. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, ICALP, Part I, pages 352-363, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_30.
  7. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210-223, 2017. URL: http://dx.doi.org/10.1145/3055399.3055502.
  8. 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, March 8-11, 2017, Hannover, Germany, pages 25:1-25:15, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.25.
  9. Radu Curticapean and Dániel Marx. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 130-139, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.22.
  10. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1-3):315-323, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2004.08.008.
  11. Martin E. Dyer, Leslie Ann Goldberg, and Mark Jerrum. An approximation trichotomy for Boolean #CSP. J. Comput. Syst. Sci., 76(3-4):267-277, 2010. URL: http://dx.doi.org/10.1016/j.jcss.2009.08.003.
  12. Tomás Feder and Moshe 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: http://dx.doi.org/10.1137/S0097539794266766.
  13. Jirí Fiala and Jan Kratochvíl. Locally constrained graph homomorphisms - structure, complexity, and applications. Computer Science Review, 2(2):97-111, 2008. URL: http://dx.doi.org/10.1016/j.cosrev.2008.06.001.
  14. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM J. Comput., 33(4):892-922, 2004. URL: http://dx.doi.org/10.1137/S0097539703427203.
  15. Leslie Ann Goldberg and Mark Jerrum. Counting unlabelled subtrees of a tree is #P-complete. 1999. Google Scholar
  16. Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149-1178, 1989. URL: http://dx.doi.org/10.1137/0218077.
  17. Pieter W. Kasteleyn. Graph theory and crystal physics. In Graph Theory and Theoretical Physics, pages 43-110. Academic Press, 1967. Google Scholar
  18. Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155-171, 1975. URL: http://dx.doi.org/10.1145/321864.321877.
  19. Bingkai Lin. The parameterized complexity of k-biclique. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 605-615, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.41.
  20. László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321-328, 1967. Google Scholar
  21. Jaroslav Nesetril. Homomorphisms of derivative graphs. Discrete Mathematics, 1(3):257-268, 1971. URL: http://dx.doi.org/10.1016/0012-365X(71)90014-8.
  22. James G. Oxley. Matroid theory. Oxford University Press, 1992. Google Scholar
  23. Arash Rafiey, Jeff Kinne, and Tomás Feder. Dichotomy for digraph homomorphism problems. CoRR, abs/1701.02409, 2017. URL: http://arxiv.org/abs/1701.02409.
  24. Gian-Carlo Rota. On the foundations of combinatorial theory I. Theory of möbius functions. Probability theory and related fields, 2(4):340-368, 1964. Google Scholar
  25. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216-226, 1978. URL: http://dx.doi.org/10.1145/800133.804350.
  26. Richard P Stanley. Enumerative combinatorics: Volume 1. 2011. Google Scholar
  27. 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
  28. Salil P. Vadhan. The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput., 31(2):398-427, 2001. URL: http://dx.doi.org/10.1137/S0097539797321602.
  29. Leslie G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189-201, 1979. URL: http://dx.doi.org/10.1016/0304-3975(79)90044-6.
  30. Leslie G. Valiant. Accidental algorithms. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 509-517, 2006. URL: http://dx.doi.org/10.1109/FOCS.2006.7.
  31. Leslie G. Valiant. Holographic algorithms. SIAM J. Comput., 37(5):1565-1594, 2008. URL: http://dx.doi.org/10.1137/070682575.
  32. Dominic J.A. Welsh. Matroid theory. Courier Corporation, 2010. Google Scholar
  33. Mingji Xia, Peng Zhang, and Wenbo Zhao. Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci., 384(1):111-125, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.05.023.
  34. Dmitriy Zhuk. The proof of CSP dichotomy conjecture. CoRR, abs/1704.01914, 2017. URL: http://arxiv.org/abs/1704.01914.
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