On a countable family of boundary graph classes for~the~dominating set problem

G. S. Dakhno ; D. S. Malyshev

Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 1, pp. 28-39

Résumé

The hereditary class is a set of simple graphs closed under deletion of vertices; every such class is defined by the set of its minimal forbidden induced subgraphs. If this set is finite, then it is called finitely defined. The concept of a boundary class is a useful tool for analysis of the computational complexity of graph problems in the finitely defined classes family. The dominating set problem for a given graph is to determine whether it has a given-size subset of vertices such that every vertex outside the subset has at least one neighbor in the subset. Previously, exactly 4 boundary classes were known for this problem (if $\mathbb{P}\neq \mathbb{NP}$). This work considers some countable set of concrete classes of graphs and proves that each its element is a boundary class for the dominating set problem (if $\mathbb{P}\neq \mathbb{NP}$). We also prove $\mathbb{NP}$-completeness of this problem for graphs that contain neither induced 6-path nor induced 4-clique, which means that the set of known boundary classes for the dominating set problem is not complete (if $\mathbb{P}\neq \mathbb{NP}$). Bibliogr. 11.

Détail

Keywords: hereditary graph class, computational complexity, dominating set.