Polynomial algorithms for sparse spanners on subcubic graphs

期刊论文
发表日期：

2024年8月7日

查看全文

R. Gómez,
F. K. Miyazawa,
Y. Wakababayashi

摘要

Let G be a connected graph and $t \ge 1$ $t \geq 1$ a (rational) constant. A t-spanner of G is a spanning subgraph of G in which the distance between any pair of vertices is at most t times its distance in G. We address two problems on spanners. The first one, known as the minimum t-spanner problem (MinS $_t$ $_{t}$ ), seeks in a connected graph a t-spanner with the smallest possible number of edges. In the second one, called minimum cost tree t-spanner problem (MCTS $_t$ $_{t}$ ), the input graph has costs assigned to its edges and seeks a t-spanner that is a tree with minimum cost. It is an optimization version of the tree t-spanner problem (TreeS $_t$ $_{t}$ ), a decision problem concerning the existence of a t-spanner that is a tree. MinS $_t$ $_{t}$ is known to be ${\textsc {NP}}$ $NP$ -hard for every $t \ge 2$ $t \geq 2$ . On the other hand, TreeS $_t$ $_{t}$ admits a polynomial-time algorithm for $t \le 2$ $t \leq 2$ and is ${\textsc {NP}}$ $NP$ -complete for $t \ge 4$ $t \geq 4$ ; but its complexity for $t=3$ $t = 3$ remains open. We focus on the class of subcubic graphs. First, we show that for such graphs MinS $_3$ $_{3}$ can be solved in polynomial time. These results yield a practical polynomial algorithm for TreeS $_3$ $_{3}$ that is of a combinatorial nature. We also show that MCTS $_2$ $_{2}$ can be solved in polynomial time. To obtain this last result, we prove a complete linear characterization of the polytope defined by the incidence vectors of the tree 2-spanners of a subcubic graph. A recent result showing that MinS $_3$ $_{3}$ on graphs with maximum degree at most 5 is NP-hard, together with the current result on subcubic graphs, leaves open only the complexity of MinS $_3$ $_{3}$ on graphs with maximum degree 4.