Packing of maximal independent mixed arborescences

DOI10.1016/J.DAM.2020.11.009MaRDI QIDQ2217484zbMATH OpenOpenAlexFDO

Authors Hui Gao, Daqing Yang

Publication date 29 December 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.04062

zbMATH Keywords

arborescencematroidmixed graphpackingsupermodularity

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: Kir'{a}ly in [On maximal independent arborescence packing, SIAM J. Discrete. Math. 30 (4) (2016), 2107-2114] solved the following packing problem: Given a digraph $D=(V,A)$, a matroid $M$ on a set $S=s_1,ldots,s_k$ along with a map $pi:SightarrowV$, find $k$ arc-disjoint maximal arborescences $T_1,ldots,T_k$ with roots $pi(s_1),ldots,pi(s_k)$, such that, for any $vinV$, the set $s_i:vinV(T_i)$ is independent and its rank reaches the theoretical maximum. In this paper, we give a new characterization for packing of maximal independent mixed arborescences under matroid constraints. This new characterization is simplified to the form of finding a supermodular function that should be covered by an orientation of each strong component of a matroid-based rooted mixed graph. Our proofs come along with a polynomial-time algorithm. Note that our new characterization extends Kir'{a}ly's result to mixed graphs, this answers a question that has already attracted some attentions.

Recommendations

• Packing of mixed hyperarborescences with flexible roots via matroid intersection
• Packing of spanning mixed arborescences
• On reachability mixed arborescence packing
• On maximal independent arborescence packing
• Packing of arborescences with matroid constraints via matroid intersection

Cites work

• Arc-disjoint in-trees in directed graphs
• Connections in combinatorial optimization
• Covering intersecting bi-set families under matroid constraints
• scientific article; zbMATH DE number 3799695 (Why is no real title available?)
• Matroid-Based Packing of Arborescences
• Old and new results on packing arborescences in directed hypergraphs
• On maximal independent arborescence packing
• On reachability mixed arborescence packing
• Packing arborescences
• Packing branchings under cardinality constraints on their root sets
• Packing of arborescences with matroid constraints via matroid intersection
• Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries
• Supermodularity in unweighted graph optimization. I: Branchings and matchings
• Supermodularity in unweighted graph optimization. II: Matroidal term rank augmentation
• Supermodularity in unweighted graph optimization. III: Highly connected digraphs
• Variations for Lovász’ Submodular Ideas

Cited in

(13)

• Packing of mixed hyperarborescences with flexible roots via matroid intersection
• Reachability in arborescence packings
• On reachability mixed arborescence packing
• On maximal independent arborescence packing
• Packing arborescences
• Matroid-Based Packing of Arborescences
• Packing of spanning mixed arborescences
• Approximate cut \& packing ratios for multi-commodity arborescences
• Matroid-reachability-based decomposition into arborescences
• Regular packing of rooted hyperforests with root constraints in hypergraphs
• Reconfiguration of the union of arborescences
• Reconfiguration of the union of arborescences
• Packing mixed hyperarborescences

This page was built for publication: Packing of maximal independent mixed arborescences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2217484)