0
$\begingroup$

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it always imply that we have to find a polynomial time algorithm for the edge coloring of that graph? Like, is it possible to prove a graph to be in class $1$ without describing an explicit algorithm to do so, like, say by computing the Lovasz number of the line graph of the graph?

Most of the problems I have seen invariably lead me to think that one could prove the graph is in class $1$ iff there is a polynomial time algorithm to color the edges of the graph. Is this right? Thanks beforehand.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I‘m not sure I understand your question. If you want to prove that a fixed graph is class 1 (which I assume means that the number of colors equals the max degree), it is enough to give a coloring with that many colors and checking this. Checking can be done in polynomial time, implying that the problem is in NP. On the other hand, if you can find a poly time algorithm which for every graph in class 1 finds a coloring with the right number of colors, you can separate the two classes in polynomial time, thus proving P=NP (again, assuming my interpretation of „class 1“ and „class 2“ is correct). $\endgroup$
    – Patrick Schnider
    Commented Jun 2, 2020 at 10:53
  • $\begingroup$ @PatrickSchnider you interpreted the class1 and class 2 concepts right, but I think you misunderstood the question. When you say that giving a coloring with colors equal to maximum degree and then checking it, the very process of assigning that many colors to the graph satisfying the adjacency condition is NP-hard in general. What I am asking is that to prove a graph is class 1, is it necessary to give a polynomial time algorithm for such a coloring, or is it possible by not providing an algorithm as such $\endgroup$
    – vidyarthi
    Commented Jun 2, 2020 at 12:05

1 Answer 1

Reset to default
2
$\begingroup$

As written the question is ill-posed: class 1 or class 2 is a property of a particular graph, whereas polynomial time is a property of an algorithm applied to an infinite family of graphs.

Patrick Schnider points out in the comments that the first fix to the question doesn't work: if we have a polynomial time algorithm for finding a colouring when it exists, we certainly have a polynomial time algorithm for testing whether a colouring exists.

The deeper question is perhaps this. Suppose we have an efficient algorithm for determining whether a particular structure (such as a colouring of a graph) exists. Can we use the algorithm to find it?

Sometimes the answer is yes. Suppose we have an efficient algorithm for deciding whether a graph is $k$-colourable. Then we can use it to find a $k$-colouring (when it exists) of a graph $G$ as follows. Test each non-edge $e$ of $G$ to see whether $G+e$ is also $k$-colourable. If it is, switch attention to $k$-colouring $G+e$. If it isn't, move on to the next edge. Note that we never have to test an edge more than once, as if $G+e$ is not $k$-colourable then $G+H+e$ is never $k$-colourable either, for any $H$. The end-point of this process is a complete $k$-partite graph, which is easily $k$-colourable.

But sometimes the answer is no, or at least "we don't know yet". Primality testing is in P, so we have an efficient algorithm to detect whether an integer can be factorised. But we don't have an efficient (classical) algorithm to factor integers, and it's not clear that we ever will. If there was a mechanical process to go from existence of objects to providing examples then this would not be such a notoriously difficult problem.

Improve this answer
$\endgroup$
7
  • $\begingroup$ so the problem i somewhat a rephrasing of whether $P=NP$, right? $\endgroup$
    – vidyarthi
    Commented Jun 16, 2020 at 9:52
  • 1
    $\begingroup$ It is not completely clear to me how you can use a polynomial time algorithm that finds colourings if they exist to actually determine whether or not they exist. Suppose I give you the algorithm and a graph to be tested... what do you do next? $\endgroup$
    – Gordon Royle
    Commented Jun 16, 2020 at 10:33
  • 1
    $\begingroup$ @GordonRoyle, suppose I can find colourings when they exist in time at most $f(n)$. I input the graph I'm wondering about into the algorithm and try to run it for $f(n)$ steps. The possible results are that it finds a colouring, or that it fails to find a colouring, possibly because it encounters a state it doesn't know what to do with (the promise of existence having been broken). Which result I get tells me whether a colouring exists. $\endgroup$
    – Ben Barber
    Commented Jun 16, 2020 at 11:09
  • 1
    $\begingroup$ @vidyarthi, It's not unrelated, but it's not exactly the same question. I'd say it's more to do with the difference between decision problems (which just have yes/no answers) and more complicated types of question which are asking for something close to what we'd usually think of as a "computation". $\endgroup$
    – Ben Barber
    Commented Jun 16, 2020 at 11:14
  • $\begingroup$ @BenBarber But most polynomial-time algorithms only come with an $O(f(n))$ time-bound, not a precise number-of-steps bound. $\endgroup$
    – Gordon Royle
    Commented Jun 16, 2020 at 13:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .