On the complexity of some subgraph problems
We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP N P -completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g.,to obtain a linear (or O(nlogn) O ( n log n ) ) time algorithm for such problems in graphs with vertex degree bounded by 3.
spanning subgraphs chordal graphs edge-deletion spanning tree q q -trees q q q q q