On the complexity of Dominating Set for graphs with fixed diameter

DOI10.1016/J.TCS.2024.114561MaRDI QIDQ6433639zbMATH OpenOpenAlexFDO

Authors Valentin Bouquet, François Delbot, Christophe Picouleau, Stephane Rovedakis

Publication date 19 April 2023

Full work available at URL https://doi.org/10.1016/j.tcs.2024.114561

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: A set $SsubseteqV$ of a graph $G=(V,E)$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Dominating Set is the problem of deciding, given a graph $G$ and an integer $kgeq1$, if $G$ has a dominating set of size at most $k$. It is well known that this problem is $mathsfNP$-complete even for claw-free graphs. We give a complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter $d$. We show that the problem is $mathsfNP$-complete for every fixed $dge3$ and polynomial time solvable for $dle2$. To prove the case $d=2$, we show that Minimum Maximal Matching can be solved in polynomial time for $2K_2$-free graphs.

This page was built for publication: On the complexity of Dominating Set for graphs with fixed diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433639)