Out-degree reducing partitions of digraphs

Joergen Bang-Jensen 1 Stéphane Bessy 2 Frédéric Havet 3 Anders Yeo 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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 N P-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 N P-complete. This solves a problem from [6] on majority colourings.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2018, 719, pp.64-72. 〈10.1016/j.tcs.2017.11.007〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01765642
Contributeur : Frederic Havet <>
Soumis le : vendredi 13 avril 2018 - 06:58:19
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Fichier

Maxreduce2part-revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Joergen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo. Out-degree reducing partitions of digraphs. Theoretical Computer Science, Elsevier, 2018, 719, pp.64-72. 〈10.1016/j.tcs.2017.11.007〉. 〈hal-01765642〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

28