Spanning trees with restricted degrees for series-parallel graph

摘要

In this paper we deal a classical problem, degree restricted spanning trees for series-parallel graph. Our general goal is to prove the NP-completeness of restricted degree spanning trees for series-parallel graph. To define it, let G be a connected series-parallel graph. Let X be a vertex subset of G and f be a mapping from X to the set of natural numbers such that f(x)/spl ges/2 for all x/spl isin/X. A spanning tree T of G such that f(x)/spl les/degT(x) for all x/spl isin/X where degT(x) denotes the degree of a vertex x in T. Here, T is the degree restricted spanning tree. Many combinatorial problems on general graphs are NP-complete, but when restricted to series-parallel graphs, many of the problems can be solved in polynomial time. On the other hand, very few of the problems are known to be NP-complete for series-parallel graph. We show a decision problem "Whether there exists a restricted degree spanning tree T in series-parallel graph G" is NP complete. Finally, we show a polynomial time approximate algorithm to find T from series-parallel graph G.