Testing for dense subsets in a graph via the partition function

Abstract: For a set

S

of vertices of a graph

G

, we define its density

0 l e q s i g m a (S) l e q 1

as the ratio of the number of edges of

G

spanned by the vertices of

S

to

| S | c h o o s e 2

. We show that, given a graph

G

with

n

vertices and an integer

m

, the partition function

s u m_{S} e x p g a m m a m s i g m a (S)

, where the sum is taken over all

m

-subsets

S

of vertices and

0 < g a m m a < 1

is fixed in advance, can be approximated within relative error

0 < e p s i l o n < 1

in quasi-polynomial

n^{O (l n m - l n e p s i l o n)}

time. We discuss numerical experiments and observe that for the random graph

G (n, 1 / 2)

one can afford a much larger

g a m m a

, provided the ratio

n / m

is sufficiently large.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Testing for dense subsets in a graph via the partition function