35
An example is this paper:
Guruswami, V., & Khanna, S. (2004). On the hardness of 4-coloring a 3-colorable graph. SIAM Journal on Discrete Mathematics, 18(1): 30-40. link
Using the PCP-Theorem, Khanna, Linial, and Safra (2000) proved that it is NP-hard to color a
3-colorable graph using just 4 colors. Later, Guruswami & Khanna (2004) gave, among ...
18
This is NP-hard. See:
Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7
The reduction is from Vertex Cover and is very nice.
Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j < n+...
17
Yes, the number of sets m in a set-cover instance is polynomial in the number of elements.
By the way -- the state of the art hardness results for Set-Cover are:
With Noga Alon and Muli Safra, we showed how to use the Raz-Safra/Arora-Sudan PCP to get a better constant $c$ in the hardness factor $c\log n$.
http://people.csail.mit.edu/dmoshkov/papers/k-...
15
For the maximum edge disjoint paths problem in directed graphs the paper of Ma & Wang (2000) was based on the label cover problem which in turn is based on the PCP theorem. Subsequently a simple reduction via the 2-disjointpath problem hardness was found by Guruswami et. al. (2003) which gave improved hardness as well.
15
An earlier version of this answer was originally posted as an answer to the question “Consequences of Unique Games being a NPI problem” by NicosM. Because it turned out that it did not answer what he wanted to ask, I moved it to this question.
Short answer: They mean different statements. The latter implies the former, but the former does not necessarily ...
14
Yes, by a reduction from MaxCut to triangle-free MaxCut. Here is what Wikipedia calls an L-reduction
Given an instance $G$ of Max-Cut, construct the 3-stretch $G'$ by subdividing each edge into three edges. Then the order of the maximum cut of $G'$ is the order of the maximum cut of $G$ plus twice the number of edges in $G$. Since the size of a max ...
13
On the positive side, it is decidable whether a one-tape Turing machine runs in time $n \mapsto C \cdot n + D$ for given $C, D \in \mathbb{N}$, see:
David Gajser: Verifying whether One-Tape Non-Deterministic Turing Machines Run in Time $Cn+D$, arXiv:1312.0496
13
There are examples from approximate counting. Approximately counting the number of satisfying assignments of an NP-relation can only be harder than deciding whether a satisfying assignment exists, so it's not too surprising that one doesn't need the PCP theorem to prove hardness for such problems. Still, the PCP theorem sometimes gives a convenient starting ...
12
The most relevant paper I know is
"The Complexity of Making Unique Choices: Approximating 1-in-k SAT" by Guruswami and Trevisan (link)
They give an algorithm for satisfiable instances which for $k=3$ would achieve a ratio of $\frac{4}{9}$, beating the random assignment. They also mention that 1-in-3 SAT is $\frac{5}{6}$-inapproximable, but I'm not sure if ...
12
The answer for (1) is "unlikely".
It is simple to show (reduce from $Partition$) there exists no $\alpha$-approximation for Bin Packing, for any $\alpha<\frac{3}{2}$, unless $P=NP$.
That said, Crescenzi et al. have shown that unless the polynomial hierarchy collapses, Bin Packing is not APX-Hard.
As for (2), perhaps you could phrase it as "Does not ...
11
Yes.
If I understood correctly, the proof of Theorem 1.6 in Khot (2001) establishes that it is NP-hard to distinguish between the following two cases, even if we focus on bounded-degree graphs of sufficiently high degree:
There is a $k$-colouring.
The ratio of the number of vertices to the maximum size of an independent set is at least $k^{\log(k)/25}$.
...
11
Kellerer et al. (1997) gives with accuracy $\epsilon$ a $O(\min \{ n/ \epsilon, n + 1/ \epsilon^2 \log(1/ \epsilon) \})$ time and $O(n + 1/ \epsilon)$ space approximation scheme.
Further improving on this, Kellerer et al. (2003) gives a FPTAS with $O(\min \{n \cdot 1/ \epsilon , n + 1/ \epsilon^2 \log( 1/ \epsilon) \} )$ time and $O(n+1/ \epsilon)$ space. ...
11
Here are the references:
S. Khanna, N. Linial, and S. Safra, On the hardness of approximating the chromatic number,
Combinatoria, 20 (2000), pp. 393–415.
C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, J.
ACM, 41 (1994), pp. 960–981.
11
There are much stronger results for approximate graph coloring.
S. Khot, Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. show that for all sufficiently large constants $k$ it is NP-hard to color a $k$-colorable graph with $k^{\Omega(log k)}$ colors
A very recent result of S. Huang Improved Hardness of ...
11
Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach.
This has been observed, for instance, in Theorem 17 in
Pierluigi Crescenzi and LucaTrevisan:
"Max NP-completeness made easy"
Theoretical Computer Science 28, (1999), Pages 65-79
10
A particularly striking example of a phase transition is the maximum degree bound for Exactly-$k$-SAT (X$k$SAT), in which each clause contains exactly $k$ distinct literals. The problem flips from being trivially easy (always satisfiable) to being NP-complete by adding one to the associated parameter.
Let $f(k)$ denote the largest number such that any X$k$...
10
Another answer, which is in a somewhat different spirit than the previous answers, is this paper of Uri Feige:
Relations between Average Case Complexity and Approximation Complexity.
Uri shows that average case assumptions can replace the PCP theorem for proving hardness of approximation of some problems.
Note, however, that we don't know how to prove the ...
10
If I understood well the problem, perhaps this is an idea for a reduction from the Hamiltonian path problem: given $G$ with $|V| = n$, a source and target node $s, t \in V$; you can extend it adding a $(n-1) \times n$ "full" grid graph having the bottom-left node of the last row connected to $s$ and the bottom right node of the last row connected to $t$.
...
10
One paper that gives an answer to this question is Chalermsook, Laekhanukit, & Nanongkai (2013).
There are also related works in the context of Fixed Parameter Tractability such as
Hajiaghayi, Khandekar, & Kortsarz (2013) and Chitnis, Hajiaghayi, Kortsarz (2013).
These hardness results are proven under various assumptions such as ETH or existence of ...
10
We're interested in additive approximations to #3SAT. i.e. given a 3CNF $\phi$ on $n$ variables count the number of satisfying assignments (call this $a$) up to additive error $k$.
Here are some basic results for this:
Case 1: $k=2^{n-1}-\mathrm{poly}(n)$
Here there is a deterministic poly-time algorithm: Let $m=2^n-2k = \mathrm{poly}(n)$. Now evaluate $\...
10
Let me see if I can clarify this, on a high level. Assume the UG instance is a bipartite graph $G = (V \cup W, E)$, bijections $\{\pi_e\}_{e \in E}$, where $\pi_e\colon \Sigma \to \Sigma$, and $|\Sigma| = m$. You want to construct a new graph $H$ so that if the UG instance is $1-\delta$ satisfiable, then $H$ has a large cut, and if the UG instance is not ...
10
There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition. This is due to Ramana. (For another take on this involving SOS, see [KS12].) To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me.
One notable consequence of this work is ...
10
Cormen, Leiserson, Rivest and Stein say that this algorithm that achieves ratio of 2 is tight. They did not exclude the possibility of another algorithm achieving better.
Vertex Cover is NP-hard to approximate with a factor better than 1.36:
http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf
Also check the following paper which give ...
9
The best algorithm I am aware of is the algorithm by Zwick, which gives $3/4$ approximation for satisfiable instances. It is presented in
Uri Zwick. “Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint.” In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.
I don't know ...
9
As David pointed out, Khot's paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring", Theorem 1.6, says it is NP-hard to color $K$-colorable graph with $2^{\Omega((\log K)^2)}$ colors for graphs with degree at most $2^{2^{(\log K)^2}}$, for sufficiently large constant $K$. In other words, for graphs of ...
9
If $p$ is constant, then the size of the maximum clique in the $G(n,p)$ model is almost everywhere a constant multiple of $\log n$, with the constant proportional to $\log (1/p)$. (See Bollobás, p.283 and Corollary 11.2.) Changing $p$ should therefore not affect the hardness of planting a clique with $\omega(\log n)$ vertices as long as the clique is too ...
9
For the SDP in standard form
$$
\min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\},
$$
Slater's condition reduces to the existence of a positive definite $X\succ 0$ that satisfies the affine constraints $\mathrm{tr}(A_i^T X) = b_i$. I would guess this is satisfied for any SDP you can find in the ...
8
There is no approximation algorithm for MIN-3CNF-DELETION at all since it is not even possible to determine in polynomial time whether a 3 CNF SAT instance is satisfiable or not (if P≠NP). That is, it is not possible to determine if the objective function is equal to 0 or strictly positive. Specifically, if we had an $f(n)$ approximation algorithm for the ...
8
The best published results all appear in a 1997 paper by Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky.
For any fixed $\varepsilon>0$, computing the genus of a graph with additive error $O(n^\varepsilon)$ is NP-hard.
There is a trivial linear-time algorithm to embed any $n$-vertex graph of (unknown) genus $g$ on an orientable surface of genus $\max\{...
8
I can recommend my recent paper http://arxiv.org/abs/1110.6832 on multicommodity flows and cuts in polymatroidal networks; we generalize several known results in standard graphs. Although we do not give a nice table summary we discuss many of the known cases. Some of the results that are not discussed in the paper but are of relevance are those for planar ...
Only top voted, non community-wiki answers of a minimum length are eligible
