Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation

Publication date: 22 February 2021

Abstract: For a fixed positive

e p s i l o n

, we show the existence of a constant

C_{e} p s i l o n

with the following property: Given a

p m 1

-edge-labeling

c : E (K_{n}) o - 1, 1

of the complete graph

K_{n}

with

c (E (K_{n})) = 0

, and a spanning forest

F

of

K_{n}

of maximum degree

D e l t a

, one can determine in polynomial time an isomorphic copy

F^{'}

of

F

in

K_{n}

with

| c (E (F^{'})) | l e q l e f t (f r a c 34 + e p s i l o n i g h t) D e l t a + C_{e} p s i l o n .

Our approach is based on the method of conditional expectation.

This page was built for publication: Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation