2018/11/30 by Alessandra Graf, Penny Haxell
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Dominating set #Efficient algorithm #Graph #Independent set #Limits and Structures in Graph Theory #Partition (number theory) #Set (abstract data type) #Vertex (graph theory) #cs.DM #math.CO #msc:05C69
paper · pdf · doi:10.1017/s0963548320000127
published as Combinator. Probab. Comp. 29 (2020) 780-806 · This new version fixes a few typos and adds a brief overview of the analysis to Section 5. There is also further discussion of future work in Section 8
openalex created_date 2018/11/16 · arxiv created 2020/02/27 · openalex publication_date 2020/05/14 · arxiv updated 2020/09/16 · openalex updated_date 2026/08/05
Abstract We give an efficient algorithm that, given a graph G and a partition V 1 ,…, V m of its vertex set, finds either an independent transversal (an independent set v 1 ,…, v m in G such that vi ∈ Vi for each i ), or a subset \cal B of vertex classes such that the subgraph of G induced by \bigcup\nolimits\cal B has a small dominating set. A non-algorithmic proof of this result has been known for a number of years and has been used to solve many other problems. Thus we are able to give algorithmic versions of many of these applications, a few of which we describe explicitly here.