Independent domination in finitely defined classes of graphs: Polynomial algorithms

We study the problem of finding in a graph an inclusionwise maximal independent set of minimum cardinality, known as minimum maximal independent set or independent dominating set problem. This is one of the hardest problems in algorithmic graph theory. In particular, restricted to the class of so called SAT-graphs, this problem coincides with satisfiability, the central problem of theoretical computer science. The class of SAT-graphs, and many other important graph classes, such as graphs of bounded vertex degree or line graphs, can be characterized by finitely many forbidden induced subgraphs. We call such classes finitely defined. The paper [R. Boliac and V. Lozin, Independent domination in finitely defined classes of graphs, Theoretical Computer Science, 301 (2003) 271-284] reveals various conditions under which the independent dominating set problem remains NP-hard in a finitely defined class. In the present paper, we identify a number of finitely defined classes where the problem admits polynomial-time solutions. In particular, we prove that the problem is solvable in polynomial time in the class of P 2 + P 3 -free graphs by correcting a mistake of the first two authors of the paper in their earlier solution. This result is in a sharp contrast with the fact that in the class of P 3 + P 3 -free graphs the problem is known to be NP-hard, since this class contains all SAT-graphs.