Lehman's Theorem and the Directed Steiner Tree Problem
| Autor: | Jochen Könemann, Laura Sanità, Bertrand Guenin, Andreas Emil Feldmann, Ahmad Abdi |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Linear programming General Mathematics Minimum weight Digraph 0102 computer and information sciences 02 engineering and technology Mathematical proof 01 natural sciences Tree (graph theory) Steiner tree problem Combinatorics symbols.namesake Terminal (electronics) 010201 computation theory & mathematics Terminal and nonterminal symbols 0202 electrical engineering electronic engineering information engineering symbols 020201 artificial intelligence & image processing QA Mathematics Mathematics |
| Zdroj: | SIAM Journal on Discrete Mathematics. 30:141-153 |
| ISSN: | 1095-7146 0895-4801 |
| Popis: | In the directed Steiner tree problem, we are given a digraph, nonnegative arc weights, a subset of vertices called terminals, and a special terminal called the root. The goal is to compute a minimum weight directed tree that connects each terminal to the root. We study the classical directed cut linear programming (LP) formulation which has a variable for every arc, and a constraint for every cut that separates a terminal from the root. For what instances is the directed cut LP integral? In this paper we demonstrate how the celebrated theorem of Lehman [Math. Program., 17 (1979), pp. 403--417] on minimally nonideal clutters provides a framework for deriving answers to this question. Specifically, we show that this framework yields short proofs of the optimum arborescences theorem and the integrality result for series-parallel digraphs. Furthermore, we use this framework to show that the directed cut linear program is integral for digraphs that are acyclic and have at most two nonterminal vertices. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|