# 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 '14 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) – Marzio De Biasi Jun 15 '14 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. – Mohammad Al-Turkistany Jun 17 '14 at 10:57
• The extension version of NP-hard problems are NP-hard (do greedy search for certificate using the oracle). – Kaveh Apr 6 '17 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). – Joshua Grochow Apr 7 '17 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.