PreprintCC BY 4.0arXiv
Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum s-Plex Problem
Abstract
Building on a new regularized continuous formulation which avoids spurious solutions of the maximum s-plex problem, we develop a tailored block-coordinate first-order method that combines away-step Frank-Wolfe updates on the standard simplex with linear optimization over the fractional b-matching polytope. We establish finite stabilization of the auxiliary variables, convergence to stationary points, and finite support identification under suitable conditions. Numerical experiments on standard benchmark graphs show that, also in practice, regularization avoids the support-identification failures observed with the original cubic formulation and enables the proposed method to quickly find high-quality s-plexes.
Related
- Maximum index of unbalanced signed graphs without a positive odd cycle
- Solving the Tikhonov Regularization of the Total Least Squares Problem by matrix simultaneous diagonalization via congruence
- Inverse eigenvalue problem for discrete three-diagonal Schroedinger operator and the continuum limit in Tikhonov regularization approach
- Alternative Tikhonov-Type Regularization for the Calderón Inverse Conductivity Problem
- Fading regularization method for the stationary Stokes data assimilation problem
BibTeX
@misc{bellesso2026breaking,
title = {{Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum $s$-Plex Problem}},
author = {Eleonora Bellesso and Immanuel M. Bomze and Francesco Rinaldi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10205},
eprint = {2610.10205},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10205},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum s-Plex Problem
AU - Eleonora Bellesso
AU - Immanuel M. Bomze
AU - Francesco Rinaldi
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10205
UR - https://arxiv.org/abs/2610.10205
AB - Building on a new regularized continuous formulation which avoids spurious solutions of the maximum s-plex problem, we develop a tailored block-coordinate first-order method that combines away-step Frank-Wolfe updates on the standard simplex with linear optimization over the fractional b-matching polytope. We establish finite stabilization of the auxiliary variables, convergence to stationary points, and finite support identification under suitable conditions. Numerical experiments on standard benchmark graphs show that, also in practice, regularization avoids the support-identification failures observed with the original cubic formulation and enables the proposed method to quickly find high-quality s-plexes.
ER -