Inapproximability proof of DSTLB and USTLB in planar graphs

Dimitri Watel (1) , Marc-Antoine Weisser (1) , Cédric Bentz (2)

1 E3S - Supélec Sciences des Systèmes
2 CEDRIC - Centre d'études et de recherche en informatique et communications

This document proves the problem of finding a minimum cost Steiner Tree covering k terminals with at most p branching nodes (with outdegree greater than 1), in a directed or an undirected planar graph with n nodes, is hard to approximate within a better ratio than n, even when the parameter p is fixed.

Domaines: Complexité [cs.CC]

Dimitri Watel, Marc-Antoine Weisser, Cédric Bentz. Inapproximability proof of DSTLB and USTLB in planar graphs. 2013. ⟨hal-00793424v1⟩