The Generalized Subgraph Problem: Complexity, Approximability and Polyhedra
Corinne Feremans, Martine Labbé, Adam N. Letchford, Juan‐José Salazar‐González · 2003
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 N P-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.