License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.25
URN: urn:nbn:de:0030-drops-70080
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7008/
Go to the corresponding LIPIcs Volume Portal

Curticapean, Radu ; Dell, Holger ; Roth, Marc

Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes

pdf-format:
LIPIcs-STACS-2017-25.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{curticapean_et_al:LIPIcs:2017:7008,
  author =	{Radu Curticapean and Holger Dell and Marc Roth},
  title =	{{Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte ValleĢe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7008},
  URN =		{urn:nbn:de:0030-drops-70080},
  doi =		{10.4230/LIPIcs.STACS.2017.25},
  annote =	{Keywords: matchings, homomorphisms, line graphs, counting complexity,   parameterized complexity}
}

Keywords: matchings, homomorphisms, line graphs, counting complexity, parameterized complexity
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI