Name
Abstract | ||
|---|---|---|
Let k be a fixed integer. We determine the complexity of finding a p-partition (V1,…,Vp) of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by Vi, (1≤i≤p) is at least k smaller than the maximum out-degree of D. We show that this problem is polynomial-time solvable when p≥2k and NP-complete otherwise. The result for k=1 and p=2 answers a question posed in [3]. We also determine, for all fixed non-negative integers k1,k2,p, the complexity of deciding whether a given digraph of maximum out-degree p has a 2-partition (V1,V2) such that the digraph induced by Vi has maximum out-degree at most ki for i∈[2]. It follows from this characterization that the problem of deciding whether a digraph has a 2-partition (V1,V2) such that each vertex v∈Vi has at least as many neighbours in the set V3−i as in Vi, for i=1,2 is NP-complete. This solves a problem from [6] on majority colourings. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.tcs.2017.11.007 | Theoretical Computer Science |
Keywords | DocType | Volume |
2-partition,Maximum out-degree reducing partition,NP-complete,Polynomial algorithm | Journal | 719 |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.41 |
References | Authors | |
4 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jørgen Bang-Jensen | 1 | 573 | 68.96 |
| Stéphane Bessy | 2 | 117 | 19.68 |
| Frédéric Havet | 3 | 433 | 55.15 |
| A. Yeo | 4 | 72 | 9.18 |