Budgeted Maximal Graph Coverage

Please always quote using this URN: urn:nbn:de:0297-zib-6918
  • An instance of the \emph{maximum coverage} problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is specified by the nodes of a graph, while the family of covering sets is restricted to connected subgraphs. We show that on general graphs the problem is polynomial time solvable if restricted to sets of size at most~$2$, but becomes NP-hard if sets of size~$3$ are permitted. On trees, we prove polynomial time solvability if each node appears in a fixed number of sets. In contrast, if vertices are allowed to appear an unbounded number of times, the problem is NP-hard even on stars. We finally give polynomial time algorithms for special cases where the subgraphs form paths and the host graph is a line, a cycle or a star.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Sven O. Krumke, Madhav V. Marathe, Diana Poensgen, Sekharipuram S. Ravi, Hans-Christoph Wirth
Document Type:ZIB-Report
Tag:approximation algorithm; budgeted maximum coverage; dynamic programming
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) [See also 68Q15]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Date of first Publication:2002/05/07
Series (Serial Number):ZIB-Report (02-24)
Published in:Appeared in: Graph-Theoretic Concepts in Computer Science. 28th Intern. Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002; revised papers. L. Kucera (ed.) Springer 2002. LNCS 2573. Pp. 321-332