<p>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. </p>

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

CC BY-SA 3.0
2017-08-23T04:36:45.653Z
2017-08-23T04:36:45.653Z
Gamow
<p>This should be indeed NP-hard. And the construction is very similar to one that already worked for a similar question: <a href="https://cstheory.stackexchange.com/questions/30605/many-one-reduction-from-inequality-problem-to-equality-problem">Many-one reduction from inequality problem to equality problem</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2015-03-04T07:23:09.717Z
This "graph blow-up" trick was very nice. Thank you very much.
megas
CC BY-SA 3.0
2015-03-06T08:49:50.150Z
Moreover, this construction is simply the microstructure of the CSP $K_k \to G$, i.e. Clique.
András Salamon
CC BY-SA 3.0
2015-03-04T07:08:45.370Z
2015-03-06T08:41:40.570Z
2017-04-13T12:32:28.077Z
Thomas S
<p>Is the decision whether a $k$-clique exists in a $k$-partite graph NP-hard? </p>

<p>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. </p>

<p><strong>Note:</strong> This is an edit of my earlier question: <em>whether the max-clique problem in a $k$-partite graph is NP-hard</em>, 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$?</p>

CC BY-SA 3.0
2015-03-04T02:11:22.023Z
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).
Austin Buchanan
CC BY-SA 3.0
2015-03-04T02:18:53.530Z
Of course.. silly me.
megas
CC BY-SA 3.0
2015-03-04T03:10:04.600Z
@AustinBuchanan I have changed the question to reflect a more specific problem I was interested in. Is the new question equally trivial?
megas
CC BY-SA 3.0
2015-03-06T22:24:58.223Z
@Saeed My comment was correct, according to the original question. Should I delete it to avoid future confusion?
Austin Buchanan
CC BY-SA 3.0
2015-03-07T08:48:12.097Z
@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).
Saeed
CC BY-SA 3.0
2017-08-22T19:08:10.773Z
K-Partite graph can be either complete or incomplete. For complete k-partite graph, we can find the k-clique in O(N^3). For incomplete k-partite graph, deciding whether a graph has k-clique or not is not polynomial. for more info read [here](https://github.com/SubbuN/Clique/raw/master/doc/slides/MaximumClique.pdf).
Subramaniyan Neelagandan
<np-hardness><clique>
$k$-clique in $k$-partite graph
megas
# $k$-clique in $k$-partite graph

(Asked by: username_0 on 2015-03-04)

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$?

**Tags:** np-hardness, clique
> **Comments:**
> **username_1**: 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).  
> **username_0**: Of course.. silly me.  
> **username_0**: @AustinBuchanan I have changed the question to reflect a more specific problem I was interested in. Is the new question equally trivial?  
> **username_1**: @Saeed My comment was correct, according to the original question. Should I delete it to avoid future confusion?  
> **username_2**: @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).  
> **username_3**: K-Partite graph can be either complete or incomplete. For complete k-partite graph, we can find the k-clique in O(N^3). For incomplete k-partite graph, deciding whether a graph has k-clique or not is not polynomial. for more info read [here](https://github.com/SubbuN/Clique/raw/master/doc/slides/MaximumClique.pdf).  

---

## 2 answers

### Answer by username_5 on 2015-03-04. Score: 10 | Accepted answer

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](https://cstheory.stackexchange.com/questions/30605/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.

> **Comments:**
> **username_0**: This "graph blow-up" trick was very nice. Thank you very much.  
> **username_6**: Moreover, this construction is simply the microstructure of the CSP $K_k \to G$, i.e. Clique.  

---

### Answer by username_4 on 2017-08-23. Score: 4

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.


---

