Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Finding Dominating Induced Matchings in \(P_8\)-Free Graphs in Polynomial Time

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Let \(G=(V,E)\) be a finite undirected graph. An edge set \(E' \subseteq E\) is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of \(E'\). The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G; this problem is also known as the Efficient Edge Domination problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is \({\mathbb {NP}}\)-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three and is solvable in linear time for \(P_7\)-free graphs. However, its complexity was open for \(P_k\)-free graphs for any \(k \ge 8\); \(P_k\) denotes the chordless path with k vertices and \(k-1\) edges. We show in this paper that the weighted DIM problem is solvable in polynomial time for \(P_8\)-free graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Biggs, N.: Perfect codes in graphs. J. Comb. Theory Ser. B 15, 289–296 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  2. Brandstädt, A., Hundt, C., Nevries, R.: Efficient edge domination on hole-free graphs in polynomial time. In: Conference Proceedings LATIN 2010. Lecture Notes in Computer Science, vol. 6034, pp. 650–661 (2010)

  3. Brandstädt, A., Leitert, A., Rautenbach, D.: Efficient dominating and edge dominating sets for graphs and hypergraphs, extended abstract. In: Conference Proceedings ISAAC 2012, Taiwan. Lecture Notes in Computer Science, vol. 7676, pp. 267–277 (2012). Full version: arXiv:1207.0953v2 [cs.DM]

  4. Brandstädt, A., Mosca, R.: Dominating induced matchings for \(P_7\)-free graphs in linear time. Algorithmica 68, 998–1018 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  5. Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discrete Math. 266, 133–142 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  6. Cardoso, D.M., Korpelainen, N., Lozin, V.V.: On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Appl. Math. 159, 521–531 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Grinstead, D.L., Slater, P.L., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Inf. Process. Lett. 48, 221–228 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  8. Hertz, A., Lozin, V.V., Ries, B., Zamaraev, V., de Werra, D.: Dominating induced matchings in graphs containing no long claw. (2015). arXiv:1505.02558

  9. Korpelainen, N., Lozin, V.V., Purcell, C.: Dominating induced matchings in graphs without a skew star. J. Discrete Algorithms 26, 45–55 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. Lu, C.L., Ko, M.-T., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Appl. Math. 119(3), 227–250 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  11. Lu, C.L., Tang, C.Y.: Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Appl. Math. 87, 203–211 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  12. Spinrad, J.P., Sritharan, R.: Algorithms for weakly triangulated graphs. Discrete Appl. Math. 59, 181–191 (1995)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors gratefully thank three anonymous reviewers for their helpful comments. The second author would like to witness that he just tries to pray a lot and is not able to do anything without that.

Author information

Authors and Affiliations

  1. Institut für Informatik, Universität Rostock, A.-Einstein-Str. 22, 18051, Rostock, Germany

    Andreas Brandstädt

  2. Dipartimento di Economia, Universitá degli Studi “G. D’Annunzio”, 65121, Pescara, Italy

    Raffaele Mosca

Authors
  1. Andreas Brandstädt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raffaele Mosca
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andreas Brandstädt.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Brandstädt, A., Mosca, R. Finding Dominating Induced Matchings in \(P_8\)-Free Graphs in Polynomial Time. Algorithmica 77, 1283–1302 (2017). https://doi.org/10.1007/s00453-016-0150-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0150-y

Keywords

Search

Navigation