131. On a Generalization of the Maximum Weighted Independent Set Problem
Invited abstract in session TA-2: Combinatorial Optimization, stream Discrete and Combinatorial Optimization.
Thursday, 8:45-10:15Room: H4
Authors (first author is the speaker)
| 1. | Hannah Borgmann
|
| Mathematics, RPTU Kaiserslautern-Landau | |
| 2. | Sven Krumke
|
| Mathematics, University of Kaiserslautern | |
| 3. | Luis Paquete
|
| Department of Informatics Engineering, University of Coimbra |
Abstract
Given a connected undirected graph G with node weights and a
family F of connected subgraphs of G, we study the problem of
choosing a subset of nodes of G that maximizes the total weight
whilst only containing a limited number of nodes from each given
subgraph from F. We call this problem maxFSG. MaxFSG is
a generalization of the well-known Maximum Weight Independent Set
Problem (in this case F is the set of all subgraphs induced by
edges of G) and, hence, NP-hard in general. To the best of our
knowledge, maxFSG has not been investigated before. We study some
possible restrictions on the structure of G and on the family of
subsets F and determine whether they are sufficient to
make maxFSG solvable in polynomial time on those instances or
whether the problem remains NP-hard. In particular, we show
NP-hardness of maxFSG on trees and provide a polynomial algorithm
for instances in which G is of bounded treewidth and F of
bounded node-frequency.
Keywords
- Dynamic Programming
- Graphs and Networks
Status: accepted
Back to the list of papers