Improved semidefinite programming bounds for the maximum $k$-colorable subgraph problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910188627296256 |
|---|---|
| author | Barkel, Mathijs Sotirov, Renata |
| author_facet | Barkel, Mathijs Sotirov, Renata |
| contents | We study the maximum $k$-colorable subgraph (M$k$CS) problem, which consists in finding a largest $k$-colorable induced subgraph in a given graph. We consider a Semidefinite Programming (SDP) relaxation for the M$k$CS problem and regard its resulting upper bound as a graph parameter. We present several properties of this graph parameter, from which we obtain that the M$k$CS problem is solvable in polynomial time for $k$-perfect graphs. We further derive two novel families of valid inequalities to strengthen the SDP relaxation. The first family reduces to a family of inequalities for the Boolean quadric polytope when $k = 1$, and the second family generalizes the family of rank inequalities for binary linear programming formulations of the stable set problem. We efficiently solve the strengthened SDP relaxation using a cutting-plane algorithm that is based on the Alternating Direction Method of Multipliers (ADMM). Extensive computational experiments show that the obtained upper bounds outperform the best upper bounds from the literature. To complement our SDP-based upper bounds, we propose an integer ADMM variant that uses an exact Binary Semidefinite Programming (BSDP) formulation of the M$k$CS problem to produce high-quality feasible solutions. To the best of our knowledge, this is the first application of the ADMM to compute integer solutions to a BSDP problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02456 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved semidefinite programming bounds for the maximum $k$-colorable subgraph problem Barkel, Mathijs Sotirov, Renata Optimization and Control 05C15, 05C17, 90C22, 90C27, 90C35 We study the maximum $k$-colorable subgraph (M$k$CS) problem, which consists in finding a largest $k$-colorable induced subgraph in a given graph. We consider a Semidefinite Programming (SDP) relaxation for the M$k$CS problem and regard its resulting upper bound as a graph parameter. We present several properties of this graph parameter, from which we obtain that the M$k$CS problem is solvable in polynomial time for $k$-perfect graphs. We further derive two novel families of valid inequalities to strengthen the SDP relaxation. The first family reduces to a family of inequalities for the Boolean quadric polytope when $k = 1$, and the second family generalizes the family of rank inequalities for binary linear programming formulations of the stable set problem. We efficiently solve the strengthened SDP relaxation using a cutting-plane algorithm that is based on the Alternating Direction Method of Multipliers (ADMM). Extensive computational experiments show that the obtained upper bounds outperform the best upper bounds from the literature. To complement our SDP-based upper bounds, we propose an integer ADMM variant that uses an exact Binary Semidefinite Programming (BSDP) formulation of the M$k$CS problem to produce high-quality feasible solutions. To the best of our knowledge, this is the first application of the ADMM to compute integer solutions to a BSDP problem. |
| title | Improved semidefinite programming bounds for the maximum $k$-colorable subgraph problem |
| topic | Optimization and Control 05C15, 05C17, 90C22, 90C27, 90C35 |
| url | https://arxiv.org/abs/2605.02456 |