14
$\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).

Improve this question
$\endgroup$
12
  • 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, 2014 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, 2014 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, 2014 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, 2017 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, 2017 at 14:55

1 Answer 1

Reset to default
10
$\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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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