Blocking optimal arborescences

DOI10.1007/978-3-642-36694-9_7zbMATH Open1396.90071arXiv1506.05677OpenAlexW2887178071MaRDI QIDQ507342FDOQ507342

Authors: Attila Bernáth, Gyula Pap, Gyula Pap 

Publication date: 3 February 2017

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Abstract: The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable in polynomial time: given a digraph $D=(V,A)$ with a designated root node $rinV$ and arc-costs $c:AomathbbR$, find a minimum cardinality subset $H$ of the arc set $A$ such that $H$ intersects every minimum $c$-cost $r$-arborescence. By an $r$-arborescence we mean a spanning arborescence of root $r$. The algorithm we give solves a weighted version as well, in which a nonnegative weight function $w:Aomathbb{R}_{+}$ (unrelated to $c$) is also given, and we want to find a subset $H$ of the arc set such that $H$ intersects every minimum $c$-cost $r$-arborescence, and $w(H)=su{m}_{ainH}w(a)$ is minimum. The running time of the algorithm is $O(n^{3}T(n,m))$, where $n$ and $m$ denote the number of nodes and arcs of the input digraph, and $T(n,m)$ is the time needed for a minimum $s-t$ cut computation in this digraph. A polyhedral description is not given, and seems rather challenging.

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

Recommendations

• Blocking optimal arborescences
• Blocking optimal \(k\)-arborescences
• The complexity of finding arborescences in hypergraphs
• Blocking unions of arborescences
• scientific article; zbMATH DE number 7692724

zbMATH Keywords

coveringpolynomial algorithmarborescences

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Cites Work

• Blockers and transversals
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• The intractability of computing the minimum distance of a code
• Title not available (Why is that?)
• Combinatorial optimization. Packing and covering
• A weighted matroid intersection algorithm
• Matching interdiction
• Finding the k most vital edges in the minimum spanning tree problem
• Increasing the Weight of Minimum Spanning Trees
• An algorithm for source location in directed graphs
• Packing rooted directed cuts in a weighted directed graph
• Computing girth and cogirth in perturbed graphic matroids
• Robustness of minimum cost arborescences
• Packing Interdiction and Partial Covering Problems
• Reliable assignments of processors to tasks and factoring on matroids

Cited In (15)

• An algorithm for optimum common root functions of two digraphs
• The Minimum Weight In-Tree Cover Problem
• Robustness of minimum cost arborescences
• Blocking unions of arborescences
• Finding minimal branchings with a given number of arcs
• Minimum Violation Vertex Maps and Their Applications to Cut Problems
• Global and fixed-terminal cuts in digraphs
• Interdicting facilities in tree networks
• Minimum \(k\) arborescences with bandwidth constraints
• Title not available (Why is that?)
• Blocking optimal structures
• Reconfiguring (non-spanning) arborescences
• The complexity of finding arborescences in hypergraphs
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• A tight \(\sqrt{2} \)-approximation for linear 3-cut

This page was built for publication: Blocking optimal arborescences

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