A set $S\subseteq V$ 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 $k\geq 1$, if $G$ has a dominating set of size at most $k$. It is well known that this problem is $\mathsf{NP}$-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 $\mathsf{NP}$-complete for every fixed $d\ge 3$ and polynomial time solvable for $d\le 2$. To prove the case $d=2$, we show that Minimum Maximal Matching can be solved in polynomial time for $2K_2$-free graphs.
翻译：一个图 $G=(V,E)$ 上的一个点集 $S\subseteq V$ 被称为支配集，如果每个顶点都有一个邻居在 $S$ 中或者它自己属于 $S$。支配集问题是给定一个图 $G$ 和一个整数 $k\geq 1$，判断 $G$ 是否有一个不超过 $k$ 个顶点的支配集。已知即使对于无爪图，该问题仍然是$\mathsf{NP}$完全的。本文对于固定直径 $d$ 的无爪图支配集问题进行了复杂性分析。我们证明对于固定的 $d\geq3$，问题具有 $\mathsf{NP}$ 完全性；对于 $d\leq2$，问题是可在多项式时间内解决的。为了证明 $d=2$ 的情况，我们证明了在 $2K_2$-free 图中 Minimum Maximal Matching 问题可以在多项式时间内解决。
相关内容
微信扫码咨询专知VIP会员