reducing $CLIQUE$ from decision to search problem - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T02:58:48Z https://cs.stackexchange.com/feeds/question/81277 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/81277 1 reducing $CLIQUE$ from decision to search problem Covvar https://cs.stackexchange.com/users/72341 2017-09-16T12:27:19Z 2017-09-16T14:17:46Z <p>consider the language:$$CLIQUE = \left\{\langle G,k\rangle \ |\ \text{ G is a graph containing a clique of size at least k } \right\}$$</p> <blockquote> <p>Suppose there's a polynomial time algorithm for $CLIQUE$. I need to show a polynomial time algorithm for finding a clique of size $k$.</p> </blockquote> <p>Now, the idea is pretty easy if there's only one clique in the graph - You remove each vertex $v_i$ and query for $CLIQUE(G_i, k)$.</p> <p>If there are two cliques in the graph this algorithm <em>could not</em> be applied since no matter which vertex will be removed there will always be a clique of size $k$.</p> <p>An alternative would be removing each one of the ${m}\choose{k}$ but if $k = n/2$ for example, that wouldn't be a polynomial time algorithm anymore.</p> <p>So my question is, can we solve this problem for the general case where there might be multiple cliques? </p> https://cs.stackexchange.com/questions/81277/-/81280#81280 1 Answer by Yuval Filmus for reducing $CLIQUE$ from decision to search problem Yuval Filmus https://cs.stackexchange.com/users/683 2017-09-16T14:17:46Z 2017-09-16T14:17:46Z <p>Keep removing vertices until the graph no longer contains a clique of size $k$, and let $v$ be the last vertex that you removed. It follows that there is some $k$-clique which contains $k$. Remove all vertices from the graph other than neighbors of $v$ (so $v$ itself is also removed), and recursively find a $(k-1)$-clique in the new graph. Add $v$ to this clique to create the desired $k$-clique.</p> <p>The algorithm can also be formulated iteratively:</p> <ol> <li>Let $C = \emptyset$ (this will be the clique).</li> <li>Let $\ell = k$ (the current size of the clique).</li> <li>Go over all vertices $v$ in the graph: <ul> <li>Check if after removing $v$ from the graph, the new graph still contains an $\ell$-clique.</li> <li>If so, continue to the next vertex.</li> <li>Otherwise, add $v$ to $C$, decrease $\ell$, and remove from the graph all vertices other than the neighbors of $v$.</li> </ul></li> <li>Return $C$.</li> </ol>