Polynomial algorithms for sparse spanners on subcubic graphs

Let G be a connected graph and $$t \ge 1$$ t ≥ 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 ≥ 2 . On the other hand, TreeS $$_t$$ t admits a polynomial-time algorithm for $$t \le 2$$ t ≤ 2 and is $${\textsc {NP}}$$ NP -complete for $$t \ge 4$$ t ≥ 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.