Revisiting the Balanced Induced Subgraph Polytope
Abstract
A signed graph G is a triple G = (V, E, s) where V is the vertex set, E is the set of undirected edges and s : E → {+, −} is a function that assigns a sign to each edge in E. Thus, E can be partitioned in two disjoint sets E + and E − , such that E + = {e ∈ E : s(e) = +} and E − = {e ∈ E : s(e) = −} and E + ∪ E − = E. We allow multiple edges in G as long as they have different signs. For convenience, denote by E + ∩ E − the set of multiple edges in E[1]. [...]
Downloads
References
Rosa M.V. Figueiredo, Martine Labbé, and Cid C. de Souza. “An exact approach to the problem of extracting an embedded network matrix”. Computers & Operations Research 38.11 (2011), pp. 1483–1492.
Frank Harary. “On the notion of balance of a signed graph.” Michigan Mathematical Journal 2.2 (1953), pp. 143–146.
Frank Harary, Meng-Hiot Lim, and Donald C. Wunsch. “Signed graphs for portfolio analysis in risk management”. IMA Journal of Management Mathematics 13.3 (2002), pp. 201–210.
Rafael Mansano et al. “Balanced portfolio via signed graphs and spectral clustering in the Brazilian stock market”. Quality & Quantity 56 (Aug. 2022), pp. 1–16.
Nikhil Bansal, Avrim Blum, and Shuchi Chawla. “Correlation clustering”. Machine learning 56.1-3 (2004), pp. 89–113.
Bhaskar DasGupta et al. “Algorithmic and complexity results for decompositions of biological networks into monotone subsystems”. Biosystems 90.1 (2007), pp. 161–178.
Francisco Barahona and Ali Ridha Mahjoub. “Facets of the balanced (acyclic) induced subgraph polytope”. Mathematical Programming 45.1 (1989), pp. 21–33.
Gérard Cornuéjols and Antonio Sassano. “On the 0, 1 facets of the set covering polytope”. Mathematical Programming 43.1 (1989), pp. 45–55.
Egon Balas and Shu Ming Ng. “On the set covering polytope: I. All the facets with coefficients in {0, 1, 2}”. Mathematical Programming 43.1 (1989), pp. 57–69.
M. Sánchez-García, M.I. Sobrón, and B. Vitoriano. “On the set covering polytope: Facets with coefficients in {0, 1, 2, 3}”. Annals of Operations Research 81.0 (1998), pp. 343–356.
