<p>Here are two references for the second part of your question.</p>

<p>The paper [1] addresses certain types of colorability of sparse graphs with given girth $g$. For every fixed $g$, they show that the associated decision problem is either trivial (every graph in the class has a coloring) or NP-complete. But determining which is the threshold value of $g$ remains a difficult open problem!<br>
<em>Edit: One of the considered problems is related to Jaeger's conjecture, that every planar graph of girth $4k$ admits a homomorphism to $C_{2k+1}$. It is shown in [1] that any counterexample directly provides a hardness proof. (A similar conjecture by Klostermeyer and Zhang exists for the odd-girth.) For the other problems considered in [1], there is no official conjecture, but for any guess about the correct threshold value $g$ that one can make, if proved false by a counterexample, the latter directly implies a corresponding hardness proof.</em></p>

<p>In the introduction of the above cited paper is also mentioned the following interesting result about SAT [2]. It is proved there that for every $k$, there exists a function $f(k)$ such that $(k,f(k))$-SAT (i.e. $k$-SAT where each variable occurs $f(k)$ times) is trivial, but $(k,f(k)+1)$-SAT is NP-complete. (The precise value of $f(k)$ seems unknown, although some estimate is given.)</p>

<p>[1] L. Esperet, M. Montassier, P. Ochem and A. Pinlou. A complexity dichotomy for the coloring of sparse graphs. Journal of Graph Theory 73:85-102, 2012. <a href="https://doi.org/10.1002/jgt.21659" rel="nofollow noreferrer">link</a> + <a href="http://www.lirmm.fr/~ochem/dichotomy.pdf" rel="nofollow noreferrer">PDF on an author's website</a></p>

<p>[2] J. Kratochvil, P. Savicky and Zs. Tuza. One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM Journal on Computing 22:203-210, 1993. <a href="https://doi.org/10.1137/0222015" rel="nofollow noreferrer">link</a></p>

CC BY-SA 3.0
2018-02-23T20:20:32.993Z
I can't see the conjectures in these examples.
Mohammad Al-Turkistany
CC BY-SA 3.0
2018-02-23T21:13:00.000Z
For [1], there is Conjecture 1 (page 1 of the paper, it's Jaeger's conjecture). Also, see the related Conjecture 19. The other problems studied there are perhaps not famous enough to have their official conjecture! Similarly for [2], I don't know if there is a conjecture about the value of f(k).
Florent Foucaud
CC BY-SA 3.0
2018-02-23T13:18:03.570Z
2018-02-24T09:58:25.620Z
2018-02-24T09:58:25.620Z
Florent Foucaud
<blockquote>
  <p>Are there common insights into the above conjectures that explain the hypothetical NP-completeness of the corresponding graph problems?</p>
</blockquote>

<p>In my opinion there is a clear common insight in the opposite direction: if the conjectures are true then the corresponding problems are not NP-complete and turn out to be trivial in both cases (they switch from NPC to $O(1)$ ).</p>

<p>And  the common insight is that the natural problems, Hamiltonian cycle and nowhere zero flow in general graphs, are "strutured and powerful" enough to efficiently "simulate" the trace of a Turing machine (à la Cook-Levin) . Then you start adding more and more constraints until you get no "computational power" at all. </p>

<p>To me it's like adding more and more constraints on the transition graph of a Turing machine (or on the read/write tape device) until you get something trivial like "the transition graph doesn't contain a cycle".</p>

<blockquote>
  <p>Are there other examples of hypothetical complexity in the above sense?</p>
</blockquote>

<p>As a (probably) "solved case" I can bring my experience related to the <a href="http://cs.smith.edu/~jorourke/TOPP/P68.html" rel="nofollow noreferrer">Rolling a Die over a Labeled Board</a> problem.</p>

<p>A few years ago it was unknown if fully labeled boards can contain two distinct Hamiltonain cycles (<em>uniquely-rollable conjecture</em> was settled for all boards with side lengths at most 8). Domotor P. (user domotorp here) and I (independently) proved that such boards exist and the conjecture is false (... note that Joseph O'Rourke hasn't updated his page yet :-).</p>

<p>Then using that fact I was able to prove that rolling a die on fully labeled board <em>with holes</em> is NP-complete (the <em>without holes</em> case is still open); though this is an unpublished result.</p>

CC BY-SA 3.0
2018-02-24T20:42:15.223Z
2018-02-24T21:16:35.490Z
2018-02-24T21:16:35.490Z
Marzio De Biasi
<p>I came across two examples of <em>hypothetical hardness</em> of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. For instance, <a href="https://en.wikipedia.org/wiki/Barnette%27s_conjecture" rel="noreferrer">Barnette's conjecture</a> states that every 3-connected cubic planar bipartite graph is Hamiltonian. <a href="https://pdfs.semanticscholar.org/b33e/22aba2254862cc1f62a44c957a4e4cb634d0.pdf" rel="noreferrer">Feder and Subi proved</a> that refuting the conjecture would imply the NP-completeness of the Hamiltonian cycle problem on graphs in the class of the conjecture.</p>

<p><a href="https://faculty.math.illinois.edu/~west/openp/tut5flow.html" rel="noreferrer">Tutte's 5-flow Conjecture</a> states that every bridgeless graph has a nowhere-zero 5-flow. Kochol showed that if the conjecture is false, then the problem of determining whether a <a href="http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1097-0118(199805)28:1%3C1::AID-JGT1%3E3.0.CO;2-Q/full" rel="noreferrer">cubic graph admits a nowhere-zero 5-flow is NP-complete</a>. </p>

<blockquote>
  <p>Are there common insights into the above conjectures that explain the hypothetical NP-completeness of the corresponding graph problems? Are there other examples of hypothetical complexity in the above sense?</p>
</blockquote>

<p>P.S. This was posted on <a href="https://mathoverflow.net/questions/288450/common-insights-into-hypothetical-complexity-of-graph-problems">MathoverFlow</a> without getting an answer.</p>

<cc.complexity-theory><graph-theory><np-hardness>
Common insights into hypothetical complexity of graph problems
Mohammad Al-Turkistany
# Common insights into hypothetical complexity of graph problems

(Asked by: username_0 on 2018-02-22)

I came across two examples of *hypothetical hardness* of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. For instance, [Barnette's conjecture](https://en.wikipedia.org/wiki/Barnette%27s_conjecture) states that every 3-connected cubic planar bipartite graph is Hamiltonian. [Feder and Subi proved](https://pdfs.semanticscholar.org/b33e/22aba2254862cc1f62a44c957a4e4cb634d0.pdf) that refuting the conjecture would imply the NP-completeness of the Hamiltonian cycle problem on graphs in the class of the conjecture.

[Tutte's 5-flow Conjecture](https://faculty.math.illinois.edu/~west/openp/tut5flow.html) states that every bridgeless graph has a nowhere-zero 5-flow. Kochol showed that if the conjecture is false, then the problem of determining whether a [cubic graph admits a nowhere-zero 5-flow is NP-complete](http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1097-0118(199805)28:1%3C1::AID-JGT1%3E3.0.CO;2-Q/full).

> Are there common insights into the above conjectures that explain the hypothetical NP-completeness of the corresponding graph problems? Are there other examples of hypothetical complexity in the above sense?

P.S. This was posted on [MathoverFlow](https://mathoverflow.net/questions/288450/common-insights-into-hypothetical-complexity-of-graph-problems) without getting an answer.

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


---

## 2 answers

### Answer by username_1 on 2018-02-23. Score: 2

Here are two references for the second part of your question.

The paper [1] addresses certain types of colorability of sparse graphs with given girth $g$. For every fixed $g$, they show that the associated decision problem is either trivial (every graph in the class has a coloring) or NP-complete. But determining which is the threshold value of $g$ remains a difficult open problem!  
*Edit: One of the considered problems is related to Jaeger's conjecture, that every planar graph of girth $4k$ admits a homomorphism to $C\_{2k+1}$. It is shown in [1] that any counterexample directly provides a hardness proof. (A similar conjecture by Klostermeyer and Zhang exists for the odd-girth.) For the other problems considered in [1], there is no official conjecture, but for any guess about the correct threshold value $g$ that one can make, if proved false by a counterexample, the latter directly implies a corresponding hardness proof.*

In the introduction of the above cited paper is also mentioned the following interesting result about SAT [2]. It is proved there that for every $k$, there exists a function $f(k)$ such that $(k,f(k))$-SAT (i.e. $k$-SAT where each variable occurs $f(k)$ times) is trivial, but $(k,f(k)+1)$-SAT is NP-complete. (The precise value of $f(k)$ seems unknown, although some estimate is given.)

[1] L. Esperet, M. Montassier, P. Ochem and A. Pinlou. A complexity dichotomy for the coloring of sparse graphs. Journal of Graph Theory 73:85-102, 2012. [link](https://doi.org/10.1002/jgt.21659) + [PDF on an author's website](http://www.lirmm.fr/~ochem/dichotomy.pdf)

[2] J. Kratochvil, P. Savicky and Zs. Tuza. One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM Journal on Computing 22:203-210, 1993. [link](https://doi.org/10.1137/0222015)

> **Comments:**
> **username_0**: I can't see the conjectures in these examples.  
> **username_1**: For [1], there is Conjecture 1 (page 1 of the paper, it's Jaeger's conjecture). Also, see the related Conjecture 19. The other problems studied there are perhaps not famous enough to have their official conjecture! Similarly for [2], I don't know if there is a conjecture about the value of f(k).  

---

### Answer by username_2 on 2018-02-24. Score: 0

> Are there common insights into the above conjectures that explain the hypothetical NP-completeness of the corresponding graph problems?

In my opinion there is a clear common insight in the opposite direction: if the conjectures are true then the corresponding problems are not NP-complete and turn out to be trivial in both cases (they switch from NPC to $O(1)$ ).

And the common insight is that the natural problems, Hamiltonian cycle and nowhere zero flow in general graphs, are "strutured and powerful" enough to efficiently "simulate" the trace of a Turing machine (à la Cook-Levin) . Then you start adding more and more constraints until you get no "computational power" at all.

To me it's like adding more and more constraints on the transition graph of a Turing machine (or on the read/write tape device) until you get something trivial like "the transition graph doesn't contain a cycle".

> Are there other examples of hypothetical complexity in the above sense?

As a (probably) "solved case" I can bring my experience related to the [Rolling a Die over a Labeled Board](http://cs.smith.edu/~jorourke/TOPP/P68.html) problem.

A few years ago it was unknown if fully labeled boards can contain two distinct Hamiltonain cycles (*uniquely-rollable conjecture* was settled for all boards with side lengths at most 8). Domotor P. (user domotorp here) and I (independently) proved that such boards exist and the conjecture is false (... note that Joseph O'Rourke hasn't updated his page yet :-).

Then using that fact I was able to prove that rolling a die on fully labeled board *with holes* is NP-complete (the *without holes* case is still open); though this is an unpublished result.


---

