Complete complexity dichotomies for the dominating set problem

G. S. Dakhno^a, D. S. Malyshev<sup>ab

a</sup> National Research University – Higher School of Economics in Nizhny Novgorod
^b Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region

Abstract: A hereditary class is a set of simple graphs closed under the removal of vertices; every such class is defined by the set of its minimal forbidden induced subgraphs. The dominating set problem for a given graph is to determine whether this graph contains a set of vertices of a given size such that each vertex outside this set has at least one neighbor belonging to it. The hereditary classes defined by five-vertex minimal forbidden induced subgraphs have been completely classified according to the algorithmic complexity of this problem. In the paper, complete complexity dichotomies are obtained for sets of forbidden induced subgraphs on at most six vertices each of which contains a five-vertex path or the result of a single subdivision of an edge of the three-leaf star.

Keywords: computational complexity, hereditary class, dominating set.

UDC: 519.17

MSC: 05C69

Received: 01.03.2024
Revised: 05.07.2024

DOI: 10.4213/mzm14308

 English version: Mathematical Notes, 2025, 117:1, 62–74

Bibliographic databases:

• 
•