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 states that every 3-connected cubic planar bipartite graph is Hamiltonian. Feder and Subi proved 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 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.

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 without getting an answer.


2 Answers 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 + PDF on an author's website

[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

  • $\begingroup$ I can't see the conjectures in these examples. $\endgroup$ Feb 23, 2018 at 20:20
  • 1
    $\begingroup$ 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). $\endgroup$ Feb 23, 2018 at 21:13

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


Your Answer

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

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