2006/11/15 by Maxim A. Babenko, Babenko, Maxim A., Pavel V. Nalivaiko +1
Mathematics · #05C85 #90C27 #90C35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C85 #msc:90C27 #msc:90C35
paper · pdf · doi:10.48550/arxiv.math/0611460
12 pages
arxiv created 2006/11/15 · arxiv updated 2009/12/01
Given a digraph G = (VG, AG), a branching in G is a set of arcs B ⊆ AG such that the underlying undirected graph spanned by B is acyclic and each node in G is entered (covered) by at most one arc from B. Tarjan developed efficient algorithms (based on the cycle contraction technique) for the following problem: given a digraph G with a weight function w \colon AG → \R, find a branching B of the minimum weight w(B) := ∑a ∈ B w(a) among all branchings with the maximum ardinality \absB. We generalize this notion as follows: for a digraph G and a matroid \calMV on VG, a matroid branching in G w.r.t. \calMV is a branching in G such that the covered set of nodes is independent w.r.t. \calMV. The unweighted (cardinality) problem consists in finding a matroid branching B with \absB maximum. We show that the general cycle contraction approach is applicable to this problem and leads to an efficient algorithm (provided that an oracle is given for testing independence in the matroids arising as the result of the contraction procedure). In the weighted version we are looking for a matroid branching B that minimizes w(B) (for a given weight function w \colon AG → \R) among all matroid branchings of the maximum cardinality. We show that if \calMV is a rainbow matroid (that is, nodes of G are marked with colors and it is forbidden to cover more than one node of any color), then there exists an O(min(n2, m log n)) method, matching the complexity of Tarjan's algorithm (here n := \absVG, m := \absAG).