Complexity of Partitioning Hypergraphs

Abstract

For a given $\pi =({\pi }_0,{\pi }_1,...,{\pi }_k)\in \{0,1,\ast {\}}^{k+1}$, we want to determine whether an input $k$-uniform hypergraph $G=(V,E)$ has a partition $(V_1,V_2)$ of the vertex set so that for all $X\subseteq V$ of size $k$, $X\in E$ if ${\pi }_{|X\cap V_1|}=1$ and $X\notin E$ if ${\pi }_{|X\cap V_1|}=0$. We prove that this problem is either polynomial-time solvable or NP-complete depending on $\pi$ when $k=3$ or $4$. We also extend this result into $k$-uniform hypergraphs for $k\ge 5$.

9pages