<p>The problem is NP-hard for $k=3$ already.</p>

<p>Indeed, testing if a graph is tripartite (i.e., there exists a partition $V_1 \sqcup V_2 \sqcup V_3$ of its vertex set $V$ such that each edge is between two different subsets) is cleary NP-hard, as it is exactly equivalent to $3$-coloring.</p>

<p>Now, I reduce the problem of the question to that problem. Given a graph $G$, construct the 3-uniform hypergraph $H$ by adding to each edge $e = \{v_1, v_2\}$ a fresh vertex $v_e$. I claim that $H$ is tripartite iff $G$ is. Indeed, a tripartition of $H$ clearly gives a tripartition of $G$. Conversely, given a tripartition of $G$, we can construct a tripartition of $H$ by assigning each fresh vertex $v_e$ to the one available class of the partition. The reduction is obviously PTIME.</p>

CC BY-SA 3.0
2016-06-19T21:06:54.567Z
Incredible, but just know I've noticed the first related question TCS offers on the right is exactly the same as mine and it is also answered, even a solution practically identical to yours is there!
domotorp
CC BY-SA 3.0
2016-06-20T03:42:36.693Z
@Ricky: Are you sure? See also this answer: http://cstheory.stackexchange.com/a/353/419
domotorp
CC BY-SA 3.0
2016-06-19T21:04:12.633Z
2016-06-19T21:04:12.633Z
Antoine Amarilli 'a3nm'
<p>We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied.
It's also in <strong>P</strong>, right? What about larger $k$?</p>

CC BY-SA 3.0
2016-06-19T18:11:29.203Z
What do you mean by uniform?
Erfan Khaniki
CC BY-SA 3.0
2016-06-19T18:19:17.217Z
@Erfan: oops, I forgot to write hyper, thx.
domotorp
CC BY-SA 3.0
2016-06-19T20:56:39.817Z
Testing whether a graph is tripartite is already NP-hard, and isn't a graph tripartite iff the hypergraph constructed by adding a fresh vertex to each edge is also tripartite? (Clearly a tripartition of the graph gives one of the hypergraph by choosing the available part for the fresh vertices, and conversely a tripartition of the hypergraph gives one of the graph.) Am I missing something?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2016-06-19T20:59:45.513Z
@a3nm: Looks pretty convincing! (typo: bip should be trip)
domotorp
CC BY-SA 3.0
2016-06-19T21:04:43.773Z
@domotorp: Fixed the typo and posted as an answer.
Antoine Amarilli 'a3nm'
<cc.complexity-theory><graph-theory><np-hardness><graph-colouring><hypergraphs>
What is the recognition complexity of k-uniform k-partite hypergraphs?
domotorp
# What is the recognition complexity of k-uniform k-partite hypergraphs?

(Asked by: username_0 on 2016-06-19)

We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied.
It's also in **P**, right? What about larger $k$?

**Tags:** cc.complexity-theory, graph-theory, np-hardness, graph-colouring, hypergraphs
> **Comments:**
> **username_1**: What do you mean by uniform?  
> **username_0**: @Erfan: oops, I forgot to write hyper, thx.  
> **username_2**: Testing whether a graph is tripartite is already NP-hard, and isn't a graph tripartite iff the hypergraph constructed by adding a fresh vertex to each edge is also tripartite? (Clearly a tripartition of the graph gives one of the hypergraph by choosing the available part for the fresh vertices, and conversely a tripartition of the hypergraph gives one of the graph.) Am I missing something?  
> **username_0**: @a3nm: Looks pretty convincing! (typo: bip should be trip)  
> **username_2**: @domotorp: Fixed the typo and posted as an answer.  

---

## 1 answers

### Answer by username_2 on 2016-06-19. Score: 2 | Accepted answer

The problem is NP-hard for $k=3$ already.

Indeed, testing if a graph is tripartite (i.e., there exists a partition $V\_1 \sqcup V\_2 \sqcup V\_3$ of its vertex set $V$ such that each edge is between two different subsets) is cleary NP-hard, as it is exactly equivalent to $3$-coloring.

Now, I reduce the problem of the question to that problem. Given a graph $G$, construct the 3-uniform hypergraph $H$ by adding to each edge $e = \{v\_1, v\_2\}$ a fresh vertex $v\_e$. I claim that $H$ is tripartite iff $G$ is. Indeed, a tripartition of $H$ clearly gives a tripartition of $G$. Conversely, given a tripartition of $G$, we can construct a tripartition of $H$ by assigning each fresh vertex $v\_e$ to the one available class of the partition. The reduction is obviously PTIME.

> **Comments:**
> **username_0**: Incredible, but just know I've noticed the first related question TCS offers on the right is exactly the same as mine and it is also answered, even a solution practically identical to yours is there!  
> **username_0**: @Ricky: Are you sure? See also this answer: http://cstheory.stackexchange.com/a/353/419  

---

