On coloring resilient graphs

DOI10.1007/978-3-662-44465-8_44MaRDI QIDQ2922638zbMATH OpenOpenAlexFDO

Authors Jeremy Kun, Lev Reyzin

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: We introduce a new notion of resilience for constraint satisfaction problems, with the goal of more precisely determining the boundary between NP-hardness and the existence of efficient algorithms for resilient instances. In particular, we study $r$-resiliently $k$-colorable graphs, which are those $k$-colorable graphs that remain $k$-colorable even after the addition of any $r$ new edges. We prove lower bounds on the NP-hardness of coloring resiliently colorable graphs, and provide an algorithm that colors sufficiently resilient graphs. We also analyze the corresponding notion of resilience for $k$-SAT. This notion of resilience suggests an array of open questions for graph coloring and other combinatorial problems.

Recommendations

• k-resistant colorings
• On the Hardness of 4-Coloring a 3-Colorable Graph
• Improved hardness of approximating chromatic number
• New NP-hardness results for 3-coloring and 2-to-1 label cover
• Local resilience of graphs

This page was built for publication: On coloring resilient graphs

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