Max Clique
Interactive proofs and the hardness of approximating cliques
https://dl.acm.org/doi/pdf/10.1145/226643.226652
The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP languages is constructed, where the verifier uses very few random bits and communication bits. Last, the connection between cliques and efficient multi-prover interaction proofs, is shown to yield hardness results on the complexity of approximating the size of the largest clique in a graph.
Why is maximum clique often easy in practice?
To this day, the maximum clique problem remains a computationally challenging problem. Indeed, despite researchers’ best efforts, there exist unsolved benchmark instances with one thousand vertices. However, relatively simple algorithms solve real-life instances with millions of vertices in a few seconds. Why is this the case? Why is the problem apparently so easy in many naturally occurring networks?
In this paper, we provide an explanation. First, we observe that the graph’s clique
number ω is very near to the graph’s degeneracy d in most real-life instances. This observation motivates a main contribution of this paper, which is an algorithm for the maximum clique problem that runs in time polynomial in the size of the graph, but exponential in the gap g := (d + 1) − ω between the clique number ω and its degeneracy-based upper bound d + 1. When this gap g can be treated as a constant, as is often the case for real-life graphs, the proposed algorithm runs in
time O(dm) = O(m1.5).
This provides a rigorous explanation for the apparent easiness of these
instances despite the intractability of the problem in the worst case. Further, our implementation of the proposed algorithm is actually practical—competitive with the best approaches from the literature.
Free Bits, PCPs and Non-Approximability – Towards Tight Results
The first part of this paper presents new proof systems and improved non-approximability results. In particular we present a proof system for using logarithmic randomness and two amortized free bits, so that Max Clique is hard within and Chromatic Number within . We also show hardness
of for Max-3-SAT, for Vertex Cover, for Max-Cut, and for Max-2-SAT.
The second part of this paper presents a “reverse” of the FGLSS connection by showing that an NP-hardness result for the approximation of MaxClique to within a factor of would imply a probabilistic verifier for NP with logarithmic randomness and amortized free-bit complexity . We also show that “existing techniques” won’t yield proof systems of less than two bits in amortized free bit complexity.
Finally, we initiate a comprehensive study of PCP and FPCP parameters, proving several triviality results and providing several useful transformations.
On the approximability of clique and related maximization problems
We consider approximations of the formn1oð1Þfor the Maximum Clique problem, wherenis the numberof vertices in the input graph and where the ‘‘oð1Þ’’ term goes to zero asnincreases. We show thatsufficiently strong negative results for such problems, which we callstronginapproximability results, haveinteresting consequences for exact computation. A simple sampling method underlies most of our result
On the hardness of approximation of minimum vertex cover
The PCP theorem by gap amplification
The PCP theorem [Arora and Safra 1998; Arora et. al. 1998] says that every language in NP has a witness format that can be checked probabilistically by reading only a constant number of bits from the proof. The celebrated equivalence of this theorem and inapproximability of certain optimization problems, due to Feige et al. [1996], has placed the PCP theorem at the heart of the area of inapproximability.
コメント
コメントを投稿