Optimization Online


The Generalized Subgraph Problem: Complexity, Approximability and Polyhedra

Corinne Feremans (c.feremans***at***ke.unimaas.nl)
Martine Labbé (mlabbe***at***smg.ulb.ac.be)
Adam Letchford (a.n.letchford***at***lancaster.ac.uk)
Juan José Salazar (jjsalaza***at***ull.es)

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.

Download: [PDF]

Entry Submitted: 09/16/2003
Entry Accepted: 09/16/2003
Entry Last Modified: 09/25/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society