12
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Juho Jun 15 '14 at 19:15
  • $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Jun 15 '14 at 21:55
  • $\begingroup$ @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. $\endgroup$ – Mohammad Al-Turkistany Jun 17 '14 at 10:57
  • 1
    $\begingroup$ The extension version of NP-hard problems are NP-hard (do greedy search for certificate using the oracle). $\endgroup$ – Kaveh Apr 6 '17 at 16:49
  • 2
    $\begingroup$ @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). $\endgroup$ – Joshua Grochow Apr 7 '17 at 14:55
9
$\begingroup$

n-coloring the n x n Sudoku graph is trivial, but if some of the colors are given to you (the extendability version) it becomes NP-complete.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.