4
$\begingroup$

Maybe there is a trivial answer to my question or maybe there is not any. But I ask it here and appreciate if anyone can give me a clear answer.

We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but maybe polynomial-time solvable for specific graphs.

My question is that, if we are given a graph $G=(V,E)$ (I am asking this generally but you can specifically assume the graph described here), and want to find for example minimum clique cover for this graph, how can we show that it is NP-hard (if it is)? Is there any method for that?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Interesting question. The obvious way is to check in which special class of graphs the problem can be polynomial solvable (if it can be). I.e In perfect graphs and triangle-free graphs the minimum clique cover can be found in polynomial time. I don't know if there is a generic method for that. $\endgroup$ – Laxmana Jan 21 '17 at 22:38
  • $\begingroup$ Α small clarification. The problem is proven to be NP-Hard / NP-Complete no matter what (computational complexity theory). You don't prove that the problem is NP-hard on your graph but you prove that the particular instance (or a class of instances) can be or not solvable in polynomial time. $\endgroup$ – Laxmana Jan 21 '17 at 22:44
  • $\begingroup$ @Laxmana Yes, checking whether the graph of my problem belongs to the special class was the first thing that I checked. But, if not, what is the next step? $\endgroup$ – m0_as Jan 22 '17 at 0:13
  • 1
    $\begingroup$ @Laxmana Regarding your second comment, you are somehow right, but assume that you have a practical problem that you have modeled it as a graph problem and the solution to the practical problem is the same as finding minimum clique cover for this graph. Then, it is a quite reasonable question to ask whether the practical problem is NP-hard/NP-complete. In that case, the fact that the minimum clique cover is generally NP-hard is not useful for you, because your are dealing with a particular graph. $\endgroup$ – m0_as Jan 22 '17 at 0:17
  • 2
    $\begingroup$ Are you asking about a decision problem on a restricted, but infinitely large, class of graphs or on a finite class of graphs? In the latter case the problem is solvable in constant time. $\endgroup$ – Pontus Jan 22 '17 at 9:02
6
$\begingroup$

There's no such thing as a hard instance. You can always figure out the answer to that one instance and then hard-code that into an algorithm. For example, you can always have an algorithm for SAT that says

if input="(XvY)^(!Xv!YvZ)"
    return SATISFIABLE
else
    [loop through all possible variable assignments]

Incidentally, this is why nobody looks at "best-case complexity", since any algorithm can be adapted to run in best-case constant time in this way. (Constant because you only have to read a fixed amount of the input to see if it's one of the ones that you have a hard-coded answer for.)

There's a category error in asking if an instance can be NP-complete. Recall the definition of what NP-completeness is:

A language $L$ is NP-complete if is in NP and every other language in NP is polynomial-time many–one reducible to $L$.

First, that statement doesn't "type-check" if you try to make $L$ be a string rather than a language. Second, the definition of many–one reductions requires that you have at least one "yes" instance and at least one "no" instance to use as targets for the reduction. One instance isn't enough to make these definitions work.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The maximum length of your hardcoded instances is some constant, so you only need to check a constant length prefix of the input. Finite languages can therefore be decided in constant time, no? $\endgroup$ – Pontus Jan 22 '17 at 13:12
  • $\begingroup$ You are right. But I didn't describe my question correctly. I updated my question. I am not asking about a specific graph. My bad. $\endgroup$ – m0_as Jan 22 '17 at 19:02
  • 1
    $\begingroup$ @m0_as Could you please ask that as a new question? Questions shouldn't be edited in a way that invalidates existing answers, so I'm reverting the edit. $\endgroup$ – David Richerby Jan 22 '17 at 19:13
  • $\begingroup$ that's right. sorry. $\endgroup$ – m0_as Jan 22 '17 at 19:14
  • 1
    $\begingroup$ @DavidRicherby :) I don't know whether there is any answer to the new question. $\endgroup$ – m0_as Jan 22 '17 at 21:46
3
$\begingroup$

A problem cannot be NP-hard for a particular graph (unless P=NP). This is because for every particular instance, there is a zero-time algorithm that solves the problem on that instance perfectly. The concept of NP-hardness only makes sense for an infinite family of instances.

In fact, much more is true. Even an uncomputable problem is computable on any given instance. Both computability and complexity are notions that only make sense in the number of instances is infinite.

We can say even more. Suppose that some problem is, indeed, NP-hard. For every particular instance we can find a constant time algorithm that solves the problem on that instance in constant time. This is because we can hardwire the solution for that particular instance.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What is a zero-time algorithm ? $\endgroup$ – Laxmana Jan 22 '17 at 11:27
  • $\begingroup$ @Laxmana For example, a Turing machine in which the initial state is also a final state. $\endgroup$ – Yuval Filmus Jan 22 '17 at 11:57
  • $\begingroup$ @YuvalFilmus So in that part of your answer you're imagining a model where the TM gives the right answer for this particular instance, but is allowed to give wrong answers for other instances? $\endgroup$ – David Richerby Jan 22 '17 at 13:29
  • $\begingroup$ @DavidRicherby Right. It's a promise problem, and the promise is that the input is that particular instance. $\endgroup$ – Yuval Filmus Jan 22 '17 at 15:38
  • 1
    $\begingroup$ @m0_as Not exactly. You can solve the problem on any specific single graph by hardcoding the answer. This only works for finitely many graphs. $\endgroup$ – Yuval Filmus Jan 22 '17 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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