7
$\begingroup$

I am not good at complexity, but got a possible relation between a plausible conjecture in graph theory and $coNP$.

Graph $G$ is Class 1 if it can be edge colored with $\Delta(G)$ colors, otherwise it is Class 2 and can be edge colored with $\Delta(G) + 1$ colors.

The Overfull conjecture (OC) asserts

A graph G with $\Delta (G) \geq n/3$ is class 2 if and only if it has an overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$.

Assume OC and $\Delta (G) \geq n/3$.

This means that we have short certificate if $G$ is Class 1 or Class 2.

For Class 1 the certificate is $\Delta(G)$ edge coloring finding it is in $NP$.

For Class 2 the certificate is overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$ and finding it is in $NP$.

This means there are no $coNP$-hard problems in this case.

There is a reduction from SAT to edge coloring $3$-regular graphs. Encoding unsatisfiable CNF to edge coloring is UNSAT and UNSAT is in $coNP$.

Question: Does the overfull conjecture and reduction from SAT to edge coloring $G$ with $\Delta (G) \geq n/3$ imply $NP=coNP$?

According to a paper edge coloring is NP-complete (possibly minor abuse of terminology) for $r$-regular graphs for any fixed $r \ge 3$ and it gives reduction of $G$ to $r$-regular $G'$.

Positive answer might help for counterexample to the overfull conjecture.

$\Delta(G)$ is the maximum degree and $n$ is the number of vertices.

EDIT Special cases of OC are proven.

According to Overfull Conjecture for Graphs with High Minimum Degree, Michael Plantholt:

we show that any (not necessarily regular) graph $G$ of even order $n$ that has sufficiently high minimum degree $\delta(G) \ge (\sqrt{7}/3) n$ has chromatic index equal to its maximum degree providing that $G$ does not contain an "overfull" subgraph, that is, a subgraph which trivially forces the chromatic index to be more than the maximum degree. This result thus verifies the Overfull Conjecture for graphs of even order and sufficiently high minimum degree.

EDIT 2 This paper p.2 might be related since it claims unless $NP=ZPP$, one can't approximate $\chi'(L^k(G))$ where $L^k(G)$ is the $k-th$ power of the line graph of $G$. (might be wrong on this since $\chi'$ is either $\Delta$ or $\Delta+1$).

Improve this question
$\endgroup$
2
  • $\begingroup$ If there non-critical mistakes in the question I would appreciate help for fixing them. $\endgroup$
    – joro
    Jun 18, 2014 at 8:31
  • $\begingroup$ Similar question on MO: mathoverflow.net/questions/346086/… $\endgroup$
    – joro
    Nov 16, 2019 at 10:44

1 Answer 1

Reset to default
5
$\begingroup$

For the possible reduction you are mentioning, if you find such a reduction from SAT to this particular edge-coloring problem, and additionnally you assume OC, then it would indeed mean NP $=$ co-NP. However, it would be very surprising: it would mean that basically, up to encoding, you found a way to always provide a short certificate that a formula is not satisfiable. This seems quite unlikely to reach with a simple construction.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thank you. So if there is SAT reduction to it (as I asked) then SAT/UNSAT in NP ∩ co-NP? $\endgroup$
    – joro
    Jun 18, 2014 at 9:22
  • $\begingroup$ Actually I misunderstood your question earlier, my answer above does not answer it. So here it is: yes it seems so, but it would be very surprising. It would mean that basically, up to encoding, you found a way to always provide a short certificate that a formula is not satisfiable. $\endgroup$
    – Denis
    Jun 18, 2014 at 9:34
  • $\begingroup$ Thank you. I don't claim it is likely both to happen (Conjecture true & SAT reduction). Though I don't find it unlikely reduction to be possible, since this will mean large degree graphs are easy to edge color (this is counterintuitive to me). $\endgroup$
    – joro
    Jun 18, 2014 at 9:41
  • 1
    $\begingroup$ Note that high degree graphs could still be hard to edge color with an optimal number of colors. It might just be easy to decide if $\Delta(G)$ colors are enough. Even this doesn't have to be the case: a problem in $\mathsf{NP} \cap \mathsf{coNP}$ doesn't have to be easy, as far as we know $\mathsf{P} \neq \mathsf{NP} \cap \mathsf{coNP}$ and we don't know an efficient algorithm for factoring yet. $\endgroup$
    – Sasho Nikolov
    Jun 18, 2014 at 15:20
  • 1
    $\begingroup$ same goes for parity games $\endgroup$
    – Denis
    Jun 18, 2014 at 16:29

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.