Kakimura, Naonori ;
Kamiyama, Naoyuki ;
Takazawa, Kenjiro
The bBranching Problem in Digraphs
Abstract
In this paper, we introduce the concept of bbranchings in digraphs, which is a generalization of branchings serving as a counterpart of bmatchings. Here b is a positive integer vector on the vertex set of a digraph, and a bbranching is defined as a common independent set of two matroids defined by b: an arc set is a bbranching if it has at most b(v) arcs sharing the terminal vertex v, and it is an independent set of a certain sparsity matroid defined by b. We demonstrate that bbranchings yield an appropriate generalization of branchings by extending several classical results on branchings. We first present a multiphase greedy algorithm for finding a maximumweight bbranching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint bbranchings. As a consequence of the packing theorem, we prove the integer decomposition property of the bbranching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b(v) arcs sharing the terminal vertex v.
BibTeX  Entry
@InProceedings{kakimura_et_al:LIPIcs:2018:9594,
author = {Naonori Kakimura and Naoyuki Kamiyama and Kenjiro Takazawa},
title = {{The bBranching Problem in Digraphs}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {12:112:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9594},
URN = {urn:nbn:de:0030drops95948},
doi = {10.4230/LIPIcs.MFCS.2018.12},
annote = {Keywords: Greedy Algorithm, Packing, Matroid Intersection, Sparsity Matroid, Arborescence}
}
27.08.2018
Keywords: 

Greedy Algorithm, Packing, Matroid Intersection, Sparsity Matroid, Arborescence 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 