k-edge subgraph problems

✍ Scribed by Olivier Goldschmidt; Dorit S. Hochbaum

• Book ID: 104294708
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 743 KB
• Volume: 74
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00030-3

✦ Synopsis

We study here a problem on graphs that involves finding a subgraph of maximum node weights spanning up to k edges. We interpret the concept of "spanning" to mean that at least one endpoint of the edge is in the subgraph in which we seek to maximize the total weight of the nodes. We discuss the complexity of this problem and other related problems with different concepts of "spanning" and show that most of these variants are NP-complete. For the problem defined, we demonstrate a factor 3 approximation algorithm with complexity O(kn) for a graph on n nodes. For the unweighted version of the the problem in a graph on m edges we describe a factor 2 approximation algorithm of greedy type, with complexity O(n + m). For trees and forests we present a polynomial time algorithm applicable to our problem and also to a problem seeking to maximize (minimize) the weight of a subtree on k nodes.