Complexity of Partitioning Hypergraphs

Publication date 21 December 2018

Abstract: For a given

p i = (p i_{0}, p i_{1}, ..., p i_{k}) i n {0, 1, *}^{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 s u b s e t e q V

of size

k

,

X i n E

if

p i_{| X c a p V_{1} |} = 1

and

X o t i n E

if

p i_{| X c a p V_{1} |} = 0

. We prove that this problem is either polynomial-time solvable or NP-complete depending on

p i

when

k = 3

or

4

. We also extend this result into

k

-uniform hypergraphs for

k g e q 5

.

This page was built for publication: Complexity of Partitioning Hypergraphs