TR-2009-04

Packing Arborescences

Kristóf Bérczi, András Frank



Abstract

Edmonds' fundamental theorem on packing arborescences has become the base of several subsequent extensions. Recently, Japanese researchers found an unexpected further generalization which gave rise to many interesting questions about this subject. Another line of researches focused on covering intersecting families which generalizes Edmonds' theorems in a different way. The two approaches was united by introducing the notion of mixed intersecting bi-set families.
 
The purpose of this paper is to overview recent developments. The presented complexity results show that finding an extension of Edmonds' theorems is not straightforward. We give a polyhedral description of arborescence packable subgraphs based on the connection with bi-set families, and -by using this description- we prove TDI-ness of the corresponding system of inequalities. We also consider the problem of independent trees and arborescences, and give a simple algorithm that decomposes a maximal planar graph into three independent trees.


Bibtex entry:

@techreport{egres-09-04,
AUTHOR = {B{\'e}rczi, Krist{\'o}f and Frank, Andr{\'a}s},
TITLE = {Packing Arborescences},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {TR-2009-04}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!