Partitioning the arcs of a digraph into a star forests of the underlying graph with prescribed orientation properties

Abstract : A star in an undirected graph is a tree in which at most one vertex has degree larger than one. A star forest is a collection of vertex disjoint stars. An out-star (in-star) in a digraph D is a star in the underlying undirected graph of D such that all edges are directed out of (into) the center. The problem of partitioning the edges of the underlying graph of a digraph D into two star forests F0 and F1 is known to be NP-complete. On the other hand, with the additional requirement for F0 and F1 to be forests of out-stars the problem becomes polynomial (via an easy reduction to 2-SAT). In this article we settle the complexity of problems lying in between these two problems. Namely, we study the complexity of the related problems where we require each Fi to be a forest of stars in the underlying sense and require (in different problems) that in D, Fi is either a forest of out-stars, in-stars, out- or in-stars or just stars in the underlying sense.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2013, 475, pp.13-20
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00807975
Contributeur : Daniel Gonçalves <>
Soumis le : jeudi 4 avril 2013 - 16:30:16
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00807975, version 1

Collections

Citation

Jørgen Bang-Jensen, Daniel Gonçalves, Anders Yeo. Partitioning the arcs of a digraph into a star forests of the underlying graph with prescribed orientation properties. Theoretical Computer Science, Elsevier, 2013, 475, pp.13-20. 〈lirmm-00807975〉

Partager

Métriques

Consultations de la notice

279