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 @math -resiliently @math -colorable graphs, which are those @math -colorable graphs that remain @math -colorable even after the addition of any @math 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 @math -SAT. This notion of resilience suggests an array of open questions for graph coloring and other combinatorial problems.
As our main results are on graph colorability, we review the relevant past work. A graph @math is @math -colorable if there is an assignment of @math distinct colors to the vertices of @math so that no edge is monochromatic. Determining whether @math is @math -colorable is a classic an NP-hard problem @cite_14 . Many attempts to simplify the problem, such as assuming planarity or bounded degree, still result in NP-hardness @cite_26 . A large body of work surrounds positive and negative results for explicit families of graphs. The list of families that are polynomial-time colorable includes triangle-free planar graphs, perfect graphs and almost-perfect graphs, bounded tree- and clique-width graphs, quadtrees, and various families of graphs defined by the lack of an induced subgraph @cite_21 @cite_6 @cite_19 @cite_27 @cite_10 .
@cite_14 @cite_26 @cite_21 @cite_6 @cite_19 @cite_27 @cite_10
1975442866 1993454521 2130673833 2167757994 1882281809
Throughout the 1960s I worked on combinatorial optimization problems including logic circuit design with Paul Roth and assembly line balancing and the traveling salesman problem with Mike Held. These experiences made me aware that seemingly simple discrete optimization problems could hold the seeds of combinatorial explosions. The work of Dantzig, Fulkerson, Hoffman, Edmonds, Lawler and other pioneers on network flows, matching and matroids acquainted me with the elegant and efficient algorithms that were sometimes possible. Jack Edmonds’ papers and a few key discussions with him drew my attention to the crucial distinction between polynomial-time and superpolynomial-time solvability. I was also influenced by Jack’s emphasis on min-max theorems as a tool for fast verification of optimal solutions, which foreshadowed Steve Cook’s definition of the complexity class NP. Another influence was George Dantzig’s suggestion that integer programming could serve as a universal format for combinatorial optimization problems. It is shown that two sorts of problems belong to the NP-complete class. First, it is proven that for a given @k-colorable graph and a given @k-coloring of that graph, determining whether the graph is or is not uniquely @k-colorable is NP-complete. Second, a result by Garey, Johnson, and Stockmeyer is extended with a proof that the coloring of four-regular planar graphs is NP-complete. For a family F of graphs and a nonnegative integer k, F + ke and F - ke, respectively, denote the families of graphs that can be obtained from F graphs by adding and deleting at most k edges, and F + kv denotes the family of graphs that can be made into F graphs by deleting at most k vertices.This paper is mainly concerned with the parameterized complexity of the vertex colouring problem on F + ke, F - ke and F - kv for various families F of graphs. In particular, it is shown that the vertex colouring problem is fixed-parameter tractable (linear time for each fixed k) for split + ke graphs and split - ke graphs, solvable in polynomial time for each fixed k but W[1]-hard for split + kv graphs. Furthermore, the problem is solvable in linear time for bipartite + 1v graphs and bipartite + 2e graphs but, surprisingly, NP-complete for bipartite + 2v graphs and bipartite + 3e graphs. We describe simple linear time algorithms for coloring the squares of balanced and unbalanced quadtrees so that no two adjacent squares are given the same color. If squares sharing sides are defined as adjacent, we color balanced quadtrees with three colors, and unbalanced quadtrees with four colors; these results are both tight, as some quadtrees require this many colors. If squares sharing corners are defined as adjacent, we color balanced or unbalanced quadtrees with six colors; for some quadtrees, at least five colors are required. We give a complete characterization of parameter graphs H for which the problem of coloring H-free graphs is polynomial and for which it is NP-complete. We further initiate a study of this problem for two forbidden subgraphs.