Polynomial algorithms for sparse spanners on subcubic graphs.

Let G be a connected graph and 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 minimumt-spanner problem (MinS t ), seeks in a connected graph a t-spanner with the smallest possible number of edges. In the second one, called minimum cost treet-spanner problem (MCTS 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 treet-spanner problem (TreeS t ), a decision problem concerning the existence of a t-spanner that is a tree. MinS t is known to be NP -hard for every t ≥ 2 . On the other hand, TreeS t admits a polynomial-time algorithm for t ≤ 2 and is NP -complete for t ≥ 4 ; but its complexity for t = 3 remains open. We focus on the class of subcubic graphs. First, we show that for such graphs MinS 3 can be solved in polynomial time. These results yield a practical polynomial algorithm for TreeS 3 that is of a combinatorial nature. We also show that MCTS 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 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 on graphs with maximum degree 4. [ABSTRACT FROM AUTHOR]