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

Jørgen Bang-Jensen, Anders Yeo, Daniel Goncalves

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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 F 0 and F 1 is known to be NP-complete. On the other hand, with the additional requirement for F0 and F 1 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 F i to be a forest of stars in the underlying sense and require (in different problems) that in D, F i is either a forest of out-stars, in-stars, out- or in-stars or just stars in the underlying sense.

OriginalsprogEngelsk
TidsskriftTheoretical Computer Science
Vol/bind475
Udgave nummerMarch
Sider (fra-til)13-20
ISSN0304-3975
DOI
StatusUdgivet - 2013

Fingeraftryk

Digraph
Stars
Partitioning
Star
Arc of a curve
Graph in graph theory
Undirected Graph
Vertex Degree
Disjoint
NP-complete problem
Polynomials

Citer dette

@article{0d2354ea14c94b5c99bd006867482064,
title = "Partitioning the arcs of a digraph into a star forest 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 F 0 and F 1 is known to be NP-complete. On the other hand, with the additional requirement for F0 and F 1 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 F i to be a forest of stars in the underlying sense and require (in different problems) that in D, F i is either a forest of out-stars, in-stars, out- or in-stars or just stars in the underlying sense.",
keywords = "2-SAT, NP-completeness proof, Star arboricity",
author = "J{\o}rgen Bang-Jensen and Anders Yeo and Daniel Goncalves",
year = "2013",
doi = "10.1016/j.tcs.2012.12.007",
language = "English",
volume = "475",
pages = "13--20",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "March",

}

Partitioning the arcs of a digraph into a star forest of the underlying graph with prescribed orientation properties. / Bang-Jensen, Jørgen; Yeo, Anders; Goncalves, Daniel .

I: Theoretical Computer Science, Bind 475, Nr. March, 2013, s. 13-20.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Partitioning the arcs of a digraph into a star forest of the underlying graph with prescribed orientation properties

AU - Bang-Jensen, Jørgen

AU - Yeo, Anders

AU - Goncalves, Daniel

PY - 2013

Y1 - 2013

N2 - 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 F 0 and F 1 is known to be NP-complete. On the other hand, with the additional requirement for F0 and F 1 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 F i to be a forest of stars in the underlying sense and require (in different problems) that in D, F i is either a forest of out-stars, in-stars, out- or in-stars or just stars in the underlying sense.

AB - 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 F 0 and F 1 is known to be NP-complete. On the other hand, with the additional requirement for F0 and F 1 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 F i to be a forest of stars in the underlying sense and require (in different problems) that in D, F i is either a forest of out-stars, in-stars, out- or in-stars or just stars in the underlying sense.

KW - 2-SAT

KW - NP-completeness proof

KW - Star arboricity

U2 - 10.1016/j.tcs.2012.12.007

DO - 10.1016/j.tcs.2012.12.007

M3 - Journal article

VL - 475

SP - 13

EP - 20

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - March

ER -