TY - JOUR

T1 - Safe sets and in-dominating sets in digraphs

AU - Bai, Yandong

AU - Bang-Jensen, Jørgen

AU - Fujita, Shinya

AU - Ono, Hirotaka

AU - Yeo, Anders

PY - 2024/3/31

Y1 - 2024/3/31

N2 - A non-empty subset S of the vertices of a digraph D is a safe set if (i) for every strongly connected component M of D−S, there exists a strongly connected component N of D[S] such that there exists an arc from M to N; and (ii) for every strongly connected component M of D−S and every strongly connected component N of D[S], we have |M|≤|N| whenever there exists an arc from M to N. In the case of acyclic digraphs a set X of vertices is a safe set precisely when X is an in-dominating set, that is, every vertex not in X has at least one arc to X. We prove that, even for acyclic digraphs which are traceable (have a hamiltonian path) it is NP-hard to find a minimum cardinality safe (in-dominating) set. Then we show that the problem is also NP-hard for tournaments and give, for every positive constant c, a polynomial algorithm for finding a minimum cardinality safe set in a tournament on n vertices in which no strong component has size more than clog(n). Under the so called Exponential Time Hypothesis (ETH) this is close to best possible in the following sense: If ETH holds, then, for every ϵ>0 there is no polynomial time algorithm for finding a minimum cardinality safe set for the class of tournaments in which the largest strong component has size at most log1+ϵ(n). We also discuss bounds on the cardinality of safe sets in tournaments.

AB - A non-empty subset S of the vertices of a digraph D is a safe set if (i) for every strongly connected component M of D−S, there exists a strongly connected component N of D[S] such that there exists an arc from M to N; and (ii) for every strongly connected component M of D−S and every strongly connected component N of D[S], we have |M|≤|N| whenever there exists an arc from M to N. In the case of acyclic digraphs a set X of vertices is a safe set precisely when X is an in-dominating set, that is, every vertex not in X has at least one arc to X. We prove that, even for acyclic digraphs which are traceable (have a hamiltonian path) it is NP-hard to find a minimum cardinality safe (in-dominating) set. Then we show that the problem is also NP-hard for tournaments and give, for every positive constant c, a polynomial algorithm for finding a minimum cardinality safe set in a tournament on n vertices in which no strong component has size more than clog(n). Under the so called Exponential Time Hypothesis (ETH) this is close to best possible in the following sense: If ETH holds, then, for every ϵ>0 there is no polynomial time algorithm for finding a minimum cardinality safe set for the class of tournaments in which the largest strong component has size at most log1+ϵ(n). We also discuss bounds on the cardinality of safe sets in tournaments.

KW - In-dominating set

KW - NP-complete

KW - Polynomial algorithm

KW - Safe set

KW - Tournament

U2 - 10.1016/j.dam.2023.12.012

DO - 10.1016/j.dam.2023.12.012

M3 - Journal article

AN - SCOPUS:85181124346

SN - 0166-218X

VL - 346

SP - 215

EP - 227

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -