Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

31.10.2018

Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes

Zeitschrift:
Theory of Computing Systems
Autoren:
Radu Curticapean, Holger Dell, Marc Roth
Wichtige Hinweise
This article is part of the Topical Collection on Special Issue on Theoretical Aspects of Computer Science (STACS 2017)
Most of this work was done while the authors were visiting the Simons Institute for the Theory of Computing. Radu Curticapean is supported by ERC grants PARAMTIGHT (No. 280152) and SYSTEMATICGRAPH (No. 725978) and VILLUM Foundation grant 16582.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

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.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit dem Kombi-Abo erhalten Sie vollen Zugriff auf über 1,8 Mio. Dokumente aus mehr als 61.000 Fachbüchern und rund 500 Fachzeitschriften aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit dem Wirtschafts-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 45.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit dem Technik-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 40.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise