2019/08/19 by Yandong Bai, Jørgen Bang-Jensen, Bai, Yandong +6
Computer Science · Mathematics · #Advanced Graph Theory Research #Cardinality (data modeling) #Combinatorics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Component (thermodynamics) #Computational Complexity (cs.CC) #Computer science #Connected component #Digraph #Discrete Mathematics (cs.DM) #Discrete mathematics #Dominating set #FOS: Computer and information sciences #FOS: Mathematics #Feedback arc set #Graph #Mathematics #Optimization and Search Problems #Strongly connected component #Time complexity #Tournament #Vertex (graph theory) #cs.CC #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1908.06664
arxiv created 2019/08/19 · openalex publication_date 2019/08/19 · arxiv updated 2019/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A non-empty subset S of the vertices of a digraph D is called a \it safe set if \beginitemize \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|≤ |N| whenever there exists an arc from M to N. \enditemize 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 ε>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.