k-edge Subgraph Problems
Abstract
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.
Download Information
Click on the following title to view and download the paper in PostScript format.
- k-edge Subgraph Problems (11 pages, 128 KB)
,
- Dorit S. Hochbaum and Olivier Goldschmidt. Discrete Applied Math, Vol. 74, No. 2, pp. 159-169 (1997).
dorit@hochbaum.ieor.berkeley.edu
7/30/98