Common insights into hypothetical complexity of graph problems

Question

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.

Answer 1

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

Answer 2

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.