Geodesic
Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1139-1162.

Voir la notice de l'article provenant de la source Library of Science

Let G = (V, E) be a finite undirected graph. An edge subset E′ ⊆ 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. The DIM problem is ℕℙ-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P7-free graphs and in polynomial time for P8-free graphs. In this paper, we solve it in polynomial time for P9-free graphs.
Keywords: dominating induced matching, P 9 -free graphs, polynomial time algorithm 
@article{DMGT_2022_42_4_a8,
     author = {Brandst\"adt, Andreas and Mosca, Raffaele},
     title = {Finding {Dominating} {Induced} {Matchings} in {P\protect\textsubscript{9}-Free} {Graphs} in {Polynomial} {Time}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1139--1162},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a8/}
}
TY  - JOUR
AU  - Brandstädt, Andreas
AU  - Mosca, Raffaele
TI  - Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1139
EP  - 1162
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a8/
LA  - en
ID  - DMGT_2022_42_4_a8
ER  - 
%0 Journal Article
%A Brandstädt, Andreas
%A Mosca, Raffaele
%T Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1139-1162
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a8/
%G en
%F DMGT_2022_42_4_a8
Brandstädt, Andreas; Mosca, Raffaele. Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1139-1162. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a8/

[1] G. Bacsó and Zs. Tuza, A characterization of graphs without long induced paths, J. Graph Theory 14 (1990) 455–464. https://doi.org/10.1002/jgt.3190140409

[2] N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 289–296. https://doi.org/10.1016/0095-8956(73)90042-7

[3] A. Brandstädt, C. Hundt and R. Nevries, Efficient edge domination on hole-free graphs in polynomial time, Conference Proceedings LATIN 2010, Lecture Notes in Comput. Sci. 6034 (2010) 650–661. https://doi.org/10.1007/978-3-642-12200-2_56

[4] A. Brandstädt and R. Mosca, Dominating induced matchings for P7-free graphs in linear time, Algorithmica 68 (2014) 998–1018. https://doi.org/10.1007/s00453-012-9709-4

[5] A. Brandstädt and R. Mosca, Finding dominating induced matchings in P8-free graphs in polynomial time, Algorithmica 77 (2017) 1283–1302. https://doi.org/10.1007/s00453-016-0150-y

[6] A. Brandstädt and R. Mosca, Dominating induced matchings in S1,2,4-free graphs, Discrete Appl. Math. 278 (2020) 83–92. https://doi.org/10.1016/j.dam.2018.09.028

[7] A. Brandstädt and R. Mosca, Finding dominating induced matchings in S2,2,3-free graphs, Discrete Appl. Math. 283 (2020) 417–434. https://doi.org/10.1016/j.dam.2020.01.028

[8] A. Brandstädt and R. Mosca, Finding dominating induced matchings in S1,1,5-free graphs, Discrete Appl. Math. 284 (2020) 269–280. https://doi.org/10.1016/j.dam.2020.03.043

[9] D.M. Cardoso, N. Korpelainen and V.V. Lozin, On the complexity of the dominating induced matching problem in hereditary classes of graphs, Discrete Appl. Math. 159 (2011) 521–531. https://doi.org/10.1016/j.dam.2010.03.011

[10] D.L. Grinstead, P.L. Slater, N.A. Sherwani and N.D. Holmes, Efficient edge domination problems in graphs, Inform. Process. Lett. 48 (1993) 221–228. https://doi.org/10.1016/0020-0190(93)90084-M

[11] A. Hertz, V.V. Lozin, B. Ries, V. Zamaraev and D. de Werra, Dominating induced matchings in graphs containing no long claw, J. Graph Theory 88 (2018) 18–39. https://doi.org/10.1002/jgt.22182

[12] N. Korpelainen, V.V. Lozin and C. Purcell, Dominating induced matchings in graphs without a skew star, J. Discrete Algorithms 26 (2014) 45–55. https://doi.org/10.1016/j.jda.2013.11.002

[13] C.L. Lu, M.-T. Ko and C.Y. Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Appl. Math. 119 (2002) 227–250. https://doi.org/10.1016/S0166-218X(01)00198-6

[14] C.L. Lu and C.Y. Tang, Solving the weighted efficient edge domination problem on bipartite permutation graphs, Discrete Appl. Math. 87 (1998) 203–211. https://doi.org/10.1016/S0166-218X(98)00057-2