The Generalized Subgraph Problem: Complexity, Approximability and Polyhedra
Corinne Feremans (c.feremanske.unimaas.nl)
Abstract: This paper is concerned with a problem on networks which we call the Generalized Subgraph Problem (GSP). The GSP is defined on an undirected graph where the vertex set is partitioned into clusters. The task is to find a subgraph which touches at most one vertex in each cluster so as to maximize the sum of vertex and edge weights. The GSP is a relaxation of several important problems of a `generalized' type and, interestingly, has strong connections with various other well-known combinatorial problems, such as the quadratic semi-assignment, max-flow / min-cut, matching, stable set, uncapacitated facility location and max-cut problems. In this paper, we examine the GSP from a theoretical viewpoint. We show that the GSP is strongly NP-hard, but solvable in polynomial time in several special cases. We also give several approximation results. Finally, we examine two 0-1 integer programming formulations and derive new classes of valid and facet-inducing inequalities that could be useful to develop a cutting plane approach for the exact or heuristic resolution of the problem.
Category 1: Combinatorial Optimization
Category 2: Combinatorial Optimization (Polyhedra )
Citation: ISRO/OR Preprint 2003/17. Universite Libre de Bruxelles, Boulevard du Triomphe, CP 210/01, 1050 Bruxelles, Belgium. September 2003.
Entry Submitted: 09/16/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|