Top

Theory of Computing Systems

Published in:

31-10-2018

Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes

Authors: Radu Curticapean, Holger Dell, Marc Roth

Published in: Theory of Computing Systems | Issue 5/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the #W[1]-hard problem of counting all matchings with exactly k edges in a given input graph G; we prove that it remains #W[1]-hard on graphs G that are line graphs or bipartite graphs with degree 2 on one side. In our proofs, we use that k-matchings in line graphs can be equivalently viewed as edge-injective homomorphisms from the disjoint union of k length-2 paths 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 \(\mathcal {H}\) of pattern graphs, we complement this result: If the graphs in \(\mathcal {H}\) have unbounded vertex-cover number even after deleting isolated edges, then counting edge-injective homomorphisms with patterns from \(\mathcal {H}\) is #W[1]-hard. Our proofs rely on an edge-colored variant of Holant problems and a delicate interpolation argument; both may be of independent interest.

previous article Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

next article Complete Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

We need to assume here that the colors of the two identified edges agree.

That is, r is bounded by dk for some overall constant d.

Here, x is an indeterminate, so the quantity (7) is a polynomial in x.

Cai, J.-Y., Zhiguo, F.: Holographic algorithm with matchgates is universal for planar #CSP over boolean domain. arXiv:abs/1603.07046 (2016)

Cai, J.-Y., Hemachandra, L.A.: On the power of parity polynomial time. Mathematical Systems Theory 23(2), 95–106 (1990). https://doi.org/10.1007/BF02090768 MathSciNetMATHCrossRef

Cai, J.-Y., Lu, P.: Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1), 41–61 (2011). https://doi.org/10.1016/j.jcss.2010.06.005 MathSciNetMATHCrossRef

Cai, J.-Y., Lu, P., Xia, M.: Holographic algorithms by Fibonacci gates and holographic reductions for hardness. In: Proceedings of the 49th Annual Symposium on Foundations of Computer Science, FOCS, pp. 644–653. https://doi.org/10.1109/FOCS.2008.34 (2008)

Cai, J.-Y., Pinyan, L., Xia, M.: Computational complexity of holant problems. SIAM J. Comput. 40(4), 1101–1132 (2011). https://doi.org/10.1137/100814585 MathSciNetMATHCrossRef

Cai, J.-Y., Pinyan, L., Xia, M.: Holographic algorithms with matchgates capture precisely tractable planar #CSP. SIAM J. Comput. 46(3), 853–889 (2017). https://doi.org/10.1137/16M1073984 MathSciNetMATHCrossRef

Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Ge, X.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216–231 (2005). https://doi.org/10.1016/j.ic.2005.05.001 MathSciNetMATHCrossRef

Chen, Y., Thurley, M., Weyer, M.: Understanding the complexity of induced subgraph isomorphisms. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP, pp. 587–596. https://doi.org/10.1007/978-3-540-70575-8_48 (2008)

Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006). https://doi.org/10.4007/annals.2006.164.51 MathSciNetMATHCrossRef

10.

Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Inf. Comput. 125(1), 1–12 (1996). https://doi.org/10.1006/inco.1996.0016 MathSciNetMATHCrossRef

11.

Curticapean, R.: Counting matchings of size k is #W[1]-hard. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP, pp. 352–363. https://doi.org/10.1007/978-3-642-39206-1_30 (2013)

12.

Curticapean, R.: The Simple, Little and Slow Things Count: on Parameterized Counting Complexity. Saarland University, PhD thesis (2015)MATH

13.

Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: Proceedings of the 49th ACM Symposium on Theory of Computing, STOC, pp. 210–223. https://doi.org/10.1145/3055399.3055502 (2017)

14.

Curticapean, R., Marx, D.: 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, pp. 130–139, IEEE. https://doi.org/10.1109/FOCS.2014.22 (2014)

15.

Curticapean, R., Xia, M.: Parameterizing the permanent Genus, apices, minors, evaluation mod 2^k. In: Proceedings of the 56th Annual Symposium on Foundations of Computer Science, FOCS, pp. 994–1009. https://doi.org/10.1109/FOCS.2015.65 (2015)

16.

Dagum, P., Luby, M.: Approximating the permanent of graphs with large factors. Theor. Comput. Sci. 102(2), 283–305 (1992). https://doi.org/10.1016/0304-3975(92)90234-7 MathSciNetMATHCrossRef

17.

Dalmau, V., Jonsson, P.: The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci. 329(1-3), 315–323 (2004). https://doi.org/10.1016/j.tcs.2004.08.008 MathSciNetMATHCrossRef

18.

Dell, H., Husfeldt, T., Marx, D., Taslaman, N., Wahlen, M.: Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algorithms 10(4), 21 (2014). https://doi.org/10.1145/2635812 MathSciNetMATHCrossRef

19.

Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892–922 (2004). https://doi.org/10.1137/S0097539703427203 MathSciNetMATHCrossRef

20.

Flum, J., Grohe, M.: Parameterized complexity theory. Springer, Berlin (2006)MATH

21.

Frick, M.: Generalized model-checking over locally tree-decomposable classes. Theor. Comput. Sci. 37(1), 157–191 (2004). https://doi.org/10.1007/s00224-003-1111-9 MathSciNetMATHCrossRef

22.

Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1), 1 (2007). https://doi.org/10.1145/1206035.1206036 MathSciNetMATHCrossRef

23.

Grohe, M., Schwentick, T., Segoufin, Luc: When is the evaluation of conjunctive queries tractable?. In: Proceedings of the 33rd ACM Symposium on Theory of Computing, STOC, pp. 657–666. https://doi.org/10.1145/380752.380867 (2001)

24.

Guruswami, V.: Maximum cut on line and total graphs. Discret. Appl. Math. 92(2-3), 217–221 (1999). https://doi.org/10.1016/S0166-218X(99)00056-6 MathSciNetMATHCrossRef

25.

Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)MATHCrossRef

26.

Jerrum, M.: Two-dimensional monomer-dimer systems are computationally intractable. J. Stat. Phys. 48(1-2), 121–134 (1987). https://doi.org/10.1007/BF01010403 MathSciNetCrossRef

27.

Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51(4), 671–697 (2004). https://doi.org/10.1145/1008731.1008738 MathSciNetMATHCrossRef

28.

Kasteleyn, P.W. : Graph theory and crystal physics. In: Graph Theory and Theoretical Physics, pp. 43–110. Academic Press (1967)

29.

Lehot, P.G.H.: An optimal algorithm to detect a line graph and output its root graph. J. ACM 21(4), 569–575 (1974). https://doi.org/10.1145/321850.321853 MathSciNetMATHCrossRef

30.

Lovász, L.: Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society. http://www.ams.org/bookstore-getitem/item=COLL-60 (2012)

31.

Lozin, V.V., Mosca, R.: Independent sets in extensions of 2K ₂-free graphs. Discret. Appl. Math. 146(1), 74–80 (2005). https://doi.org/10.1016/j.dam.2004.07.006 MATHCrossRef

32.

Meeks, K.: The challenges of unbounded treewidth in parameterised subgraph counting problems. Discret. Appl. Math. 198, 170–194 (2016). https://doi.org/10.1016/j.dam.2015.06.019 MathSciNetMATHCrossRef

33.

Roth, M.: Counting restricted homomorphisms via Möbius inversion over matroid lattices. In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pp. 63:1–63:14. https://doi.org/10.4230/LIPIcs.ESA.2017.63 (2017)

34.

Sbihi, N.: Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile. Discret. Math. 29, 53–76 (1980). https://doi.org/10.1016/0012-365X(90)90287-R MATHCrossRef

35.

Temperley, H.N.V., Fisher, M.E.: Dimer problem in statistical mechanics - an exact result. Philos. Mag. 6(68), 1478–6435 (1961). https://doi.org/10.1080/14786436108243366 MathSciNetMATHCrossRef

36.

Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31(2), 398–427 (2001). https://doi.org/10.1137/S0097539797321602 MathSciNetMATHCrossRef

37.

Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189–201 (1979). https://doi.org/10.1016/0304-3975(79)90044-6 MathSciNetMATHCrossRef

38.

Valiant, L.G.: Holographic algorithms. SIAM J. Comput. 37(5), 1565–1594 (2008). https://doi.org/10.1137/070682575 MathSciNetMATHCrossRef

39.

Šoltés, Ľ.: Forbidden induced subgraphs for line graphs. Discret. Math. 132(1), 391–394 (1994). https://doi.org/10.1016/0012-365X(92)00577-E MathSciNetMATHCrossRef

40.

Williams, V.V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42(3), 831–854 (2013). https://doi.org/10.1137/09076619X MathSciNetMATHCrossRef

41.

Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci. 384(1), 111–125 (2007). Theory and Applications of Models of Computation. https://doi.org/10.1016/j.tcs.2007.05.023 MathSciNetMATHCrossRef

42.

Zhang, X.-D., Bylka, S.: Disjoint triangles of a cubic line graph. Graphs and Combinatorics 20(2), 275–280 (2004). https://doi.org/10.1007/s00373-004-0551-6 MathSciNetMATHCrossRef

Title: Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes
Authors: Radu Curticapean
Holger Dell
Marc Roth
Publication date: 31-10-2018
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 5/2019
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9893-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 5/2019

On Long Words Avoiding Zimin Patterns

Mixing of Permutations by Biased Transpositions

Complete Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

Improved Distance Queries and Cycle Counting by Frobenius Normal Form

Guest Editorial: Special Issue on Theoretical Aspects of Computer Science

Premium Partner