| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420474 | Discrete Applied Mathematics | 2009 | 9 Pages |
Abstract
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 NPNP-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(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andrea Scozzari, Fabio Tardella,