2
$\begingroup$

A problem is defined to be in NP when it can be reduced to another NP problem in polynomial time.

In Karp's 21 NP-complete problems, the most famous ones are presented. However, I wonder (and could not find a reference) for some of them, what happens if we "relax" the objective function.

For instance, say Hamiltonian path problem: given a graph $G$ with $n$ vertices, is there a simple path $P$ of length $n$? (i.e. passes through all vertices). This problem is NP-complete.

But what if I ask for a path $P$ whose length is $n-k$? At which value of $k$ the problem becomes tractable?

Similarly, 3-coloring problem: color the vertices of a graph with three colors such that no two adjacent vertices have the same color. What if I allow $k$ pairs of adjacent vertices to be the same color?

Is this descripton the very same thing with approximation algorithms? Or is this a different concept?

$\endgroup$
  • $\begingroup$ In 3-coloring you allow an algorithm to have a bounded error which is close to approximation algorithm (I think this is close to MAX-SAT). Various problems have different parameters and their bounds also depends on some conjectures (stronger than $P\neq NP$). $\endgroup$ – rus9384 Aug 24 '17 at 15:36
  • 2
    $\begingroup$ "A problem is defined to be in NP when it can be reduced to another NP problem in polynomial time." -- that's not the definition (can you see why?) but it's a true statement. However, did you mean to write NP-complete? Then the statement is false. $\endgroup$ – Raphael Aug 24 '17 at 15:42
  • 1
    $\begingroup$ You may want to check out our reference questions to get your definitions and terminology straight. $\endgroup$ – Raphael Aug 24 '17 at 15:44
  • $\begingroup$ This is not the usual notion of approximation, in which we have an objective function that we are trying to maximize or minimize, and an approximation algorithm produces a solution whose value is within some guaranteed factor of the optimum. $\endgroup$ – Yuval Filmus Aug 24 '17 at 20:18
5
$\begingroup$

Approximation algorithms are most often encountered in the context of optimization problems. Consider the problem of minimizing some function $f$ subject to constraints $C$. An $\alpha$ approximation algorithm (where $\alpha$ can depend on some parameters of the instance, such as the number of vertices in a graph) is a (usually) polynomial time algorithm which produces a feasible solution (that is, one satisfying the constraints $C$) whose value is at most $\alpha$ times the optimum.

In some cases, bicriteria approximation algorithms are considered. These are algorithms as above, with the only difference being that the solution doesn't satisfy the constraints $C$ but rather some weaker version of them $C'$. See this question for some examples.

In the case of 3-coloring, your notion is very similar to the following optimization version of 3-coloring: given a graph, find a 3-coloring which violates the least number of constraints. There are several hardness results that show that it is difficult to approximate the optimum, even if you are allowed to use more colors (in the spirit of bicriteria optimization problems). For example, Guruswami and Khanna, in their paper On the hardness of 4-coloring a 3-colorable graph, show that it is NP-hard to distinguish between the following two classes of graphs: (i) 3-colorable graphs, (ii) graphs in which every 4-coloring has an $\epsilon_0$-fraction of monochromatic edges (for some constant $\epsilon_0$).

Similarly, your relaxation of the Hamiltonian path problem can be rephrased as an optimization problem: the longest path problem. It is NP-hard for any constant $k$, and even for much larger $k$; see the paper mentioned in Wikipedia, On approximating the longest path in a graph by Karger, Motwani and Ramkumar.

$\endgroup$
  • $\begingroup$ Do I understand that correctly: If I am given a three-colorable graph, then it is hard to find a colouring where at most eps percent of the nodes have neighbours with four different colours? $\endgroup$ – gnasher729 Aug 26 '17 at 14:00
  • $\begingroup$ No. It is hard to distinguish between 3-colorable graphs and graphs which cannot even be 4-colorable. The exact result is even stronger - the graphs in the second case not only cannot be 4-colored, but moreover any (not necessarily legal) 4-coloring has at least a constant fraction of monochromatic edges. $\endgroup$ – Yuval Filmus Aug 26 '17 at 14:09
  • $\begingroup$ You, sir, are the person who helps me the most in terms of improvement in the field. Thank you for this very good explaination. $\endgroup$ – padawan Aug 29 '17 at 21:38

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.