Safe sets in digraphs

MaRDI QIDQ6323851zbMATH OpenFDO

Authors Yandong Bai, Jørgen Bang-Jensen, Shinya Fujita, A. Yeo

Publication date 19 August 2019

Abstract: A non-empty subset $S$ of the vertices of a digraph $D$ is called a {it safe set} if �egin{itemize} item[(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 item[(ii)] for every strongly connected component $M$ of $D-S$ and every strongly connected component $N$ of $D[S]$, we have $|M|leq|N|$ whenever there exists an arc from $M$ to $N$. end{itemize} In the case of acyclic digraphs a set $X$ of vertices is a safe set precisely when $X$ is an {it 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 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 $epsilon>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 $lo{g}^{1+epsilon}(n)$. We also discuss bounds on the cardinality of safe sets in tournaments.

This page was built for publication: Safe sets in digraphs

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