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:
AUTHOR | = | {B{\'e}rczi, Krist{\'o}f and Frank, Andr{\'a}s}, |
TITLE | = | {Packing Arborescences}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2009}, |
NUMBER | = | {TR-2009-04} |