# Hard extendability problems

In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other extendability problems transform an easy problem to hard one.

For instance, Konig-Hall theorem states that all cubic bipartite graphs are 3-edge colorable but the extendability version becomes $NP$-complete if we are given the colors of some edges.

I'm looking for a survey paper of hard extendability problems where the the base problem is easy (or trivial as in the above example).

• I don't know if there is a survey of extendability problems, but at least one very well studied such problem is precoloring extension. You'll find many hits searching for the problem name.
– Juho
Jun 15, 2014 at 19:15
• Two notes: 1) are there NPC problems that cannot be transformed to a hard extendability problem? 2) I think that it would be very interesting also a survey that is focused only on extendability problems, for which the "base" problem has unknown complexity (e.g. the monochromatic rectangle free problem, or some puzzle games) Jun 15, 2014 at 21:55
• @MarzioDeBiasi Very interesting comment. 1) I do not know any such example. 2) GI is a good candidate and I guess its extendability problem is NP-complete. Jun 17, 2014 at 10:57
• The extension version of NP-hard problems are NP-hard (do greedy search for certificate using the oracle). Apr 6, 2017 at 16:49
• @MarzioDeBiasi: GI-extendability is indeed GI-complete (not just GI-hard, which I believe is what you meant to say), and therefore not NP-complete unless PH collapses. GI-extendability can be rephrased as vertex-colored GI (where vertices of a given color can only map to vertices of the same color), which reduces to GI in a number of ways (one of which is to attach gadgets to vertices, similar to your $K_n$ idea). Apr 7, 2017 at 14:55

By the "Sudoku graph" I mean the natural graph whose associated coloring problem is Sudoku. Namely, suppose $n=k^2$ is a square. The graph will have $n^2$ vertices, which we will denote by $(r_1, r_2; c_1, c_2)$ for $r_1,r_2,c_1,c_2 \in [k] = [\sqrt{n}]$. For each fixed $(r_1,r_2)$, the vertices $(r_1, r_2; *, *)$ form an $n$-clique; for each fixed $(c_1, c_2)$ the vertices $(*, *; c_1, c_2)$ form an $n$-clique; and for each fixed $(r_1, c_1)$, the vertices $(r_1, *; c_1, *)$ form an $n$-clique.