|
We introduce and study a generalization of the well-known
Steiner tree problem to count matroids.
In the count matroid ${\cal 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 ${\cal M}_{k,l}(G)$
and $|E|=k|V|-l$ holds.
Given a graph $G=(V,E)$, a non-negative length function $w:E\to \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 ${\cal 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 ${\cal 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\geq 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.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor and Kobayashi, Yusuke and Mahara, Ryoga and Makino, Kazuhisa}, |
| TITLE | = | {The Steiner problem for count matroids}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2020}, |
| NUMBER | = | {TR-2020-03} |