The Steiner Problem for Count Matroids
- 29 May 2020
- book chapter
- Published by Springer Nature
- Vol. 12126, 330-342
Abstract
We introduce and study a generalization of the well-known Steiner tree problem to count matroids. In the count matroid \(\mathcal{M}_{k,l}(G)\), defined on the edge set of a graph \(G=(V,E)\), a set \(F\subseteq E\) is independent if every vertex set \(X\subseteq V\) spans at most \(k|X|-l\) edges of F. The graph is called (k, l)-tight if its edge set is independent in \(\mathcal{M}_{k,l}(G)\) and \(|E|=k|V|-l\) holds. Given a graph \(G=(V,E)\), a non-negative length function \(w:E\rightarrow \mathbb {R}\), a set \(T\subseteq V\) of terminals and parameters k, l, our goal is to find a shortest (k, l)-tight subgraph of G that contains the terminals. Since \(\mathcal{M}_{1,1}(G)\) is isomorphic to the graphic matroid of G, the special case \(k=l=1\) corresponds to the Steiner tree problem. We obtain other interesting problems by choosing different parameters: for example, in the case \(k=2\), \(l=3\) the target is a shortest rigid subgraph containing all terminals. First we show that this problem is NP-hard even if \(k=2\), \(l=3\), and w is metric, or \(w\equiv 1\) and \(|T|=2\). As a by-product of this result we obtain that finding a shortest circuit in \(\mathcal{M}_{2,3}(G)\) is NP-hard. Then we design a \((k+1)\)-approximation algorithm for the metric version of the problem with parameters \((k,k+1)\), for all \(k\ge 2\). In particular, we obtain a 3-approximation algorithm for the Steiner version of the shortest rigid subgraph problem. We also show that the metric version can be solved in polynomial time for \(k=2\), \(l=3\), provided |T| is fixed.
Keywords
This publication has 13 references indexed in Scilit:
- Geometric Sensitivity of Rigid GraphsSIAM Journal on Discrete Mathematics, 2013
- An improved LP-based approximation for steiner tree2010
- Graph Theoretic Techniques in the Analysis of Uniquely Localizable Sensor Networks2009
- Pebble game algorithms and sparse graphsDiscrete Mathematics, 2008
- Steiner Tree Problems in Computer Communication Networks2008
- On minimally k-edge-connected graphs and shortest k-edge-connected Steiner networksDiscrete Applied Mathematics, 2003
- Constructive characterizations for packing and covering with treesDiscrete Applied Mathematics, 2003
- Algorithms for Graph Rigidity and Scene AnalysisLecture Notes in Computer Science, 2003
- A NEW BOUND FOR EUCLIDEAN STEINER MINIMAL TREESAnnals of the New York Academy of Sciences, 1985
- On graphs and rigidity of plane skeletal structuresJournal of Engineering Mathematics, 1970