Article in volume
Authors:
Title:
Finding dominating induced matchings in $P_9$-free graphs in polynomial time
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1139-1162
Received: 2019-10-07 , Revised: 2020-05-08 , Accepted: 2020-05-13 , Available online: 2020-06-08 , https://doi.org/10.7151/dmgt.2336
Abstract:
Let $G=(V,E)$ be a finite undirected graph. An edge subset $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$.
The DIM problem is \NP-complete even for very restricted graph classes such as
planar bipartite graphs with maximum degree 3 but was solved in linear time
for $P_7$-free graphs and in polynomial time for $P_8$-free graphs. In this
paper, we solve it in polynomial time for $P_9$-free graphs.
Keywords:
dominating induced matching, $P_9$-free graphs, polynomial time algorithm
References:
- 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 - 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 - 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 - A. Brandstädt and R. Mosca, Dominating induced matchings for $P_7$-free graphs in linear time, Algorithmica 68 (2014) 998–1018.
https://doi.org/10.1007/s00453-012-9709-4 - A. Brandstädt and R. Mosca, Finding dominating induced matchings in $P_8$-free graphs in polynomial time, Algorithmica 77 (2017) 1283–1302.
https://doi.org/10.1007/s00453-016-0150-y - A. Brandstädt and R. Mosca, Dominating induced matchings in $S_{1,2,4}$-free graphs, Discrete Appl. Math. 278 (2020) 83–92.
https://doi.org/10.1016/j.dam.2018.09.028 - A. Brandstädt and R. Mosca, Finding dominating induced matchings in $S_{2,2,3}$-free graphs, Discrete Appl. Math. 283 (2020) 417–434.
https://doi.org/10.1016/j.dam.2020.01.028 - A. Brandstädt and R. Mosca, Finding dominating induced matchings in $S_{1,1,5}$-free graphs, Discrete Appl. Math. 284 (2020) 269–280.
https://doi.org/10.1016/j.dam.2020.03.043 - 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 - 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 - 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 - 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 - 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 - 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
Close