New Lower Bound on Max Cut of Hypergraphs with an Application to r -Set Splitting

A classical result by Edwards states that every connected graph

G

on

n

vertices and

m

edges has a cut of size at least

$\frac{m}{2}+\frac{n-1}{4}$

. We generalize this result to

r

-hypergraphs, with a suitable notion of connectivity that coincides with the notion of connectivity on graphs for

r

 = 2. More precisely, we show that for every “partition connected”

r

-hypergraph (every hyperedge is of size at most

r

)

H

over a vertex set

V

(

H

), and edge set

E

(

H

) = {

e

1

,

e

2

,…

e

m

}, there always exists a 2-coloring of

V

(

H

) with {1, − 1} such that the number of hyperedges that have a vertex assigned 1 as well as a vertex assigned − 1 (or get “split”) is at least

$\mu_H+\frac{n-1}{r2^{r-1}}$

. Here

$\mu_H=\sum_{i=1}^{m}(1- 2/2^{|e_i|})=\sum_{i=1}^{m}(1- 2^{1-|e_i|})$

. We use our result to show that a version of

r

-Set Splitting

, namely,

Above Average

r

-Set Splitting (AA-

r

-SS)

, is fixed parameter tractable (FPT). Observe that a random 2-coloring that sets each vertex of the hypergraph

H

to 1 or − 1 with equal probability always splits at least

μ

H

hyperedges. In

AA-

r

-SS

, we are given an

r

-hypergraph

H

and a positive integer

k

and the question is whether there exists a 2-coloring of

V

(

H

) that splits at least

μ

H

 + 

k

hyperedges. We give an algorithm for

AA-

r

-SS

that runs in time

f

(

k

)

n

O

(1)

, showing that it is FPT, even when

r

 = 

c

1

log

n

, for every fixed constant

c

1

 < 1. Prior to our work

AA-

r

-SS

was known to be FPT only for constant

r

. We also complement our algorithmic result by showing that unless NP ⊆ DTIME(

n

loglog

n

),

AA-

⌈log

n

⌉

-SS

is not in

X

P.