Out-degree reducing partitions of digraphs

Abstract: Let

k

be a fixed integer. We determine the complexity of finding a

p

-partition

(V_{1}, d o t s, V_{p})

of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by

V_{i}

, (

1 l e q i l e q p

) is at least

k

smaller than the maximum out-degree of

D

. We show that this problem is polynomial-time solvable when

p g e q 2 k

and

c a l N P

-complete otherwise. The result for

k = 1

and

p = 2

answers a question posed in cite{bangTCS636}. We also determine, for all fixed non-negative integers

k_{1}, k_{2}, p

, the complexity of deciding whether a given digraph of maximum out-degree

p

has a

2

-partition

(V_{1}, V_{2})

such that the digraph induced by

V_{i}

has maximum out-degree at most

k_{i}

for

i i n [2]

. It follows from this characterization that the problem of deciding whether a digraph has a 2-partition

(V_{1}, V_{2})

such that each vertex

v i n V_{i}

has at least as many neighbours in the set

V_{3 - i}

as in

V_{i}

, for

i = 1, 2

is

c a l N P

-complete. This solves a problem from cite{kreutzerEJC24} on majority colourings.

Recommendations

Cites Work

Cited In (10)

This page was built for publication: Out-degree reducing partitions of digraphs