## Contributed Session Thu.3.H 3012

#### Thursday, 15:15 - 16:45 h, Room: H 3012

**Cluster 2: Combinatorial optimization** [...]

### Arborescences

**Chair: Attila BernĂ¡th**

**Thursday, 15:15 - 15:40 h, Room: H 3012, Talk 1**

**Attila BernĂ¡th**

Covering minimum cost arborescences

**Coauthor: Gyula Pap**

**Abstract:**

Given a digraph *D=(V,A)* with a designated root node *r ∈ V* and

arc-costs *c:A → ***R**, we consider the problem of finding a minimum

cardinality subset *H* of the arc set *A* such that *H* intersects

every minimum *c*-cost *r*-arborescence.

This problem is a special

case of covering minimum cost common bases of two matroids, which is

NP-complete even if the two matroids coincide, and the costs are all

equal to 1.

On the other hand we show that this special case is polynomially

solvable: we give a polynomial algorithm for finding such an arc

set *H*. The algorithm solves a weighted version as well, in which a

nonnegative weight function *w:A → ***R**_{+} 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)* is minimum.

**Thursday, 15:45 - 16:10 h, Room: H 3012, Talk 2**

**Mario Leston-Rey**

Packing entering sets in kernel systems

**Coauthor: Yoshiko Wakabayashi**

**Abstract:**

In 1998, H. N. Gabow and K. S. Manu showed a strongly polynomial time

algorithm to obtain - in a capacitated digraph with m arcs and

n edges - a maximum integral packing of at most *m + n - 2* arborescences. We extend their result and show that, in the more general framework of packing entering sets in kernel systems, due to A. Frank, an integral packing of size at most m can be computed in strongly polynomial time.

**Thursday, 16:15 - 16:40 h, Room: H 3012, Talk 3**

**Mikael Call**

A polyhedral analysis of a unique shortest path routing polytope

**Coauthor: Daniel Karch**

**Abstract:**

Consider a strongly connected digraph and two spanning arborescenses. The arborescenses form a unique shortest path system (USPS) if there is a vector of arc costs that simultaneously yields the arborescenses as unique shortest path arborescenses. USPSs correspond to the bases of an independence system. We characterize a large class of facet defining rank inequalities for the associated polytope. In particular, these facets can be obtained by sequential lifting of circuit inequalities. Given a circuit inequality, we determine the facet induced by an arbitrary lifting order.