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$?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ What do you mean by uniform? $\endgroup$– Erfan KhanikiCommented Jun 19, 2016 at 18:11
-
$\begingroup$ @Erfan: oops, I forgot to write hyper, thx. $\endgroup$– domotorpCommented Jun 19, 2016 at 18:19
-
$\begingroup$ 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? $\endgroup$– Antoine Amarilli 'a3nm'Commented Jun 19, 2016 at 20:56
-
$\begingroup$ @a3nm: Looks pretty convincing! (typo: bip should be trip) $\endgroup$– domotorpCommented Jun 19, 2016 at 20:59
-
$\begingroup$ @domotorp: Fixed the typo and posted as an answer. $\endgroup$– Antoine Amarilli 'a3nm'Commented Jun 19, 2016 at 21:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Jun 19, 2016 at 21:04
-
$\begingroup$ 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! $\endgroup$– domotorpCommented Jun 19, 2016 at 21:06
-
$\begingroup$ @Ricky: Are you sure? See also this answer: cstheory.stackexchange.com/a/353/419 $\endgroup$– domotorpCommented Jun 20, 2016 at 3:42
-
$\begingroup$ @domotorp : Oh, I guess this answer only describes its reduction as the wrong direction, rather than actually giving a reduction in the wrong direction. $\endgroup$– user6973Commented Jun 20, 2016 at 3:46