Article,
Safe sets and in-dominating sets in digraphs
Affiliations
- [1] Northwestern Polytechnical University [NORA names: China; Asia, East];
- [2] University of Southern Denmark [NORA names: SDU University of Southern Denmark; University; Denmark; Europe, EU; Nordic; OECD];
- [3] Yokohama City University [NORA names: Japan; Asia, East; OECD];
- [4] Nagoya University [NORA names: Japan; Asia, East; OECD];
- [5] University of Johannesburg [NORA names: South Africa; Africa]
Abstract
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 c log ( 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 log 1 + ϵ ( n ) . We also discuss bounds on the cardinality of safe sets in tournaments.