<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-04-07T14:53:50.103Z
2017-04-07T15:26:59.577Z
2017-04-07T15:26:59.577Z
Joshua Grochow
<p>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.</p>

<p>For instance, Konig-Hall theorem states that all cubic bipartite graphs
are 3-edge colorable but the <a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.10088/full" rel="nofollow noreferrer">extendability version becomes $NP$-complete</a> if we are given the colors of some edges.</p>

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

CC BY-SA 3.0
2014-06-15T19:15:45.333Z
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
CC BY-SA 3.0
2014-06-15T21:55:46.800Z
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
CC BY-SA 3.0
2014-06-17T10:57:47.270Z
@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
CC BY-SA 3.0
2014-06-17T11:07:42.437Z
A fact: GI-extendability is GI-complete. Indeed even if you don't allow an *empty partial solution* (you should specify it in the question) you can add a large enough $K_n$ to both graphs and give as partial solution the mapping between the two $K_n$. I'll think if it can be NPC!
Marzio De Biasi
CC BY-SA 3.0
2017-04-06T16:49:06.553Z
The extension version of NP-hard problems are NP-hard (do greedy search for certificate using the oracle).
Kaveh
CC BY-SA 3.0
2017-04-06T16:54:09.680Z
@Kaveh My base problem is not NP-hard. It is trivial since the edges of any bridgeless cubic graph can be partitioned into edge-disjoint paths $P_4$
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-04-06T19:28:48.897Z
the reply was to Marizo's question.
Kaveh
CC BY-SA 3.0
2017-04-07T14:36:40.603Z
Given that there seems unlikely to be a survey, and given the list that is starting to build in the comments, do you want to make this CW and ask for a big list (where a survey would of course be an acceptable answer)?
Joshua Grochow
CC BY-SA 3.0
2017-04-07T14:50:29.443Z
@JoshuaGrochow No need for CW. I am only interested in examples where the "base problem" is easy. The base problem mentioned in the post is trivial. I edited the post accordingly.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-04-07T14:55:24.210Z
@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
CC BY-SA 3.0
2017-04-07T14:56:48.513Z
Okay, no need for CW. But still: do you want a big list of easy problems whose extendability problem is NP-complete, or do you only want a survey, or do you want an answer to your specific question as to whether the particular extendability problem mentioned in the question is hard?
Joshua Grochow
CC BY-SA 3.0
2017-04-07T15:08:34.243Z
@JoshuaGrochow  I want an answer to my question? That is my priority. Your example is welcomed.
Mohammad Al-Turkistany
<cc.complexity-theory><reference-request><graph-theory><np-hardness>
Hard extendability problems
Mohammad Al-Turkistany
# Hard extendability problems

(Asked by: username_0 on 2014-06-15)

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](http://onlinelibrary.wiley.com/doi/10.1002/jgt.10088/full) 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).

**Tags:** cc.complexity-theory, reference-request, graph-theory, np-hardness

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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)  
> **username_0**: @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.  
> **username_2**: A fact: GI-extendability is GI-complete. Indeed even if you don't allow an *empty partial solution* (you should specify it in the question) you can add a large enough $K_n$ to both graphs and give as partial solution the mapping between the two $K_n$. I'll think if it can be NPC!  
> **username_3**: The extension version of NP-hard problems are NP-hard (do greedy search for certificate using the oracle).  
> **username_0**: @username_3 My base problem is not NP-hard. It is trivial since the edges of any bridgeless cubic graph can be partitioned into edge-disjoint paths $P_4$  
> **username_3**: the reply was to Marizo's question.  
> **username_4**: Given that there seems unlikely to be a survey, and given the list that is starting to build in the comments, do you want to make this CW and ask for a big list (where a survey would of course be an acceptable answer)?  
> **username_0**: @JoshuaGrochow No need for CW. I am only interested in examples where the "base problem" is easy. The base problem mentioned in the post is trivial. I edited the post accordingly.  
> **username_4**: @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).  
> **username_4**: Okay, no need for CW. But still: do you want a big list of easy problems whose extendability problem is NP-complete, or do you only want a survey, or do you want an answer to your specific question as to whether the particular extendability problem mentioned in the question is hard?  
> **username_0**: @JoshuaGrochow  I want an answer to my question? That is my priority. Your example is welcomed.  

---

## 1 answers

### Answer by username_4 on 2017-04-07. Score: 10 | Accepted answer

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.


---

