Finding independent transversals efficiently

DOI10.1017/S0963548320000127MaRDI QIDQ4987260zbMATH OpenFDO

Authors Alessandra Graf, Penny Haxell

Publication date 30 April 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.02687

zbMATH Keywords

efficient algorithmindependent transversalmaximum degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Transversal (matching) theory (05D15)

Abstract: We give an efficient algorithm that, given a graph $G$ and a partition $V_1,ldots,V_m$ of its vertex set, finds either an independent transversal (an independent set $v_1,ldots,v_m$ in $G$ such that $v_{i}in{V}_i$ for each $i$), or a subset $mathcalB$ of vertex classes such that the subgraph of $G$ induced by $$ has a small dominating set. A non-algorithmic proof of this result has been known for a number of years and has been applied 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.

Recommendations

• Independent transversals in locally sparse graphs
• Independent Transversals and Independent Coverings in Sparse Partite Graphs
• On factors of independent transversals in \(k\)-partite graphs
• Graphs of low average degree without independent transversals
• Colorings, transversals, and local sparsity

Cites work

• A condition for matchability in hypergraphs
• A constructive algorithm for the Lovász local lemma on permutations
• A constructive proof of the general Lovász local lemma
• A constructive proof of the Lovász local lemma
• A note on a conjecture of Ryser
• A note on hitting maximum and maximal cliques with a stable set
• A note on vertex list colouring
• A revival of the girth conjecture
• A sharper local lemma with improved applications
• Algorithms for Weighted Independent Transversals and Strong Colouring
• Almost perfect matchings in random uniform hypergraphs
• An algorithmic approach to the Lovász local lemma. I
• An extension of the Moser-Tardos algorithmic local lemma
• An improved bound for the strong chromatic number
• An improvement of the Lovász local lemma via cluster expansion
• Bounded size components -- partitions and transversals.
• Complete Subgraphs of r-partite Graphs
• Deterministic algorithms for the Lovász local lemma
• Edge Colouring with Delays
• Extremal problems for transversals in graphs with bounded degree
• Hall's theorem for hypergraphs
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• scientific article; zbMATH DE number 5764785 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• scientific article; zbMATH DE number 1445282 (Why is no real title available?)
• Independent systems of representatives in weighted graphs
• Independent transversals in \(r\)-partite graphs
• Lopsidependency in the Moser-Tardos framework: beyond the lopsided Lovász local lemma
• Moser and tardos meet Lovász
• Odd Independent Transversals are Odd
• On complete subgraphs of r-chromatic graphs
• On Forming Committees
• On hitting all maximum cliques with an independent set
• On the Strong Chromatic Number
• Partitioning into graphs with only small components
• Random walks that find perfect objects and the Lovász local lemma
• Ryser's conjecture for tripartite 3-graphs
• Santa claus meets hypergraph matchings
• Santa Claus Meets Hypergraph Matchings
• Sets of elements that pairwise generate a linear group
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• The circular chromatic index of graphs of high girth
• The clique complex and hypergraph matching
• The intersection of a matroid and a simplicial complex
• The linear arboricity of graphs
• The Moser--Tardos Framework with Partial Resampling
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Transversals of Vertex Partitions in Graphs
• Triangulated spheres and colored cliques

Cited in

(14)

• Bounded size components -- partitions and transversals.
• Entropy compression versus Lovász local lemma
• On factors of independent transversals in \(k\)-partite graphs
• Transversals of Vertex Partitions in Graphs
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• Algorithms for Weighted Independent Transversals and Strong Colouring
• Colorings, transversals, and local sparsity
• Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
• Graphs of low average degree without independent transversals
• Algorithms for weighted independent transversals and strong colouring
• Degree criteria and stability for independent transversals
• Constructing graphs with no independent transversals
• List packing number of bounded degree graphs
• Stability in graphs with matroid constraints

This page was built for publication: Finding independent transversals efficiently

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