2
$\begingroup$

Is the decision whether a $k$-clique exists in a $k$-partite graph NP-hard?

I have found only a very limited number of references on this problem, and they seem to be concerned with heuristics to enumerate the cliques (in particular k-cliques in k-partite graphs). On complexity, they only comment that the max-clique problem is generally hard, but nothing on the specific case.

Note: This is an edit of my earlier question: whether the max-clique problem in a $k$-partite graph is NP-hard, with $k$ being part of the input? As Austin pointed out in the comments, it is easy to see that the answer is trivially yes by a reduction from the general max-clique problem; any graph $G$ on $n$ vertices can be considered $n$-partite. The new question, however, is more specific and a reduction does not seem so obvious. For example, (and contrary to the original question) for $k=n$ one can easily check if an $n$-partite graph contains/is an $n$-clique. What about general $k$?

Improve this question
$\endgroup$
6
  • $\begingroup$ If k is part of the input, then this is exactly as hard as the maximum clique problem in arbitrary graphs (let k=n). If k is a fixed constant, then the problem is solvable in polynomial time (since the clique number will be bounded by a constant). $\endgroup$ – Austin Buchanan Mar 4 '15 at 2:11
  • $\begingroup$ Of course.. silly me. $\endgroup$ – megas Mar 4 '15 at 2:18
  • $\begingroup$ @AustinBuchanan I have changed the question to reflect a more specific problem I was interested in. Is the new question equally trivial? $\endgroup$ – megas Mar 4 '15 at 3:10
  • $\begingroup$ @Saeed My comment was correct, according to the original question. Should I delete it to avoid future confusion? $\endgroup$ – Austin Buchanan Mar 6 '15 at 22:24
  • $\begingroup$ @Austin Buchanan, yes your comment was correct but question changed (a lot) after your first ccomment and in yhe recent history of question was not obvious (except that one check very first one). I deleted my comments as they are unrelated to question (I was really confused what is going on here). $\endgroup$ – Saeed Mar 7 '15 at 8:48
9
$\begingroup$

This should be indeed NP-hard. And the construction is very similar to one that already worked for a similar question: Many-one reduction from inequality problem to equality problem.

From a graph $G=(V,E)$ and $k$ construct the graph $G'$ with vertex set $V \times \{1,\dots,k\}$ and edges between $(v,i)$ and $(w,j)$ if $(i \ne j)$ and $(v \ne w)$ and $(v,w) \in E$. It is easy to see that $G'$ is $k$-partite and it has a $k$-clique if and only if $G$ has.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This "graph blow-up" trick was very nice. Thank you very much. $\endgroup$ – megas Mar 4 '15 at 7:23
  • $\begingroup$ Moreover, this construction is simply the microstructure of the CSP $K_k \to G$, i.e. Clique. $\endgroup$ – András Salamon Mar 6 '15 at 8:49
4
$\begingroup$

The book "Computers and Intractability" by Michael Garey and David S. Johnson contains a textbook NP-hardness proof for the $k$-clique problem. If you look into this proof, you will see that the constructed graph is in fact $k$-partite.

So you get NP-hardness of deciding the existence of $k$-clique in $k$-partite graphs for free.

Improve this answer
$\endgroup$

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.