Technical Report CS0843

Authors: J.A. Makowsky and U. Rotics
Abstract: D. Peleg and A.A. Sch\"{a}ffer and Cai showed that the problem of determining, for a given graph $G$ and an integer $k$, whether $G$ has $t$-spanner with at most $k$ edges is NP-complete. D. Peleg and A.A. Sch\"{a}ffer also presented three polynomial time approximation algorithms for finding 2,3 and 5 spanners for chordal graphs having $O(|V|^{1.5}), O(|V| \log |V|)$ and $O(|V|)$ edges respectively. However, the question whether such approximation algorithms are needed remained open. We give an affirmative answer to this and show that the $t$-spanner problem is NP-hard on the class of chordal graphs. Therefore, approximation is the best one can do for the $t$-spanner problem on chordal graphs, if $P \neq NP$. Since the class of chordal graphs is a sub-class of the class of perfect graphs, it follows from our result that the $t$-spanner problem is NP-complete on the class of perfect graphs, too. Our result is somewhat surprising, as many problems, which are NP-complete on arbitrary graphs, are polynomial on chordal graphs. Among those we have Independent Set, Clique, Partition into Cliques and Chromatic Numbers. However, other known problems which are NP-complete on chordal graphs are: Hamiltonian Circuit, Dominating Set, Steiner Tree and Maximum $k$-colorable Subgraph for non-fixed $k$.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion