pith. sign in

arxiv: 2605.02456 · v1 · submitted 2026-05-04 · 🧮 math.OC

Improved semidefinite programming bounds for the maximum k-colorable subgraph problem

Mathijs Barkel , Renata Sotirov This is my paper

Pith reviewed 2026-05-08 17:38 UTC · model grok-4.3

classification 🧮 math.OC
keywords maximum k-colorable subgraphsemidefinite programmingvalid inequalitiesADMM cutting-plane algorithmk-perfect graphsbinary semidefinite programminggraph parametersstable set inequalities
0
0 comments X

The pith

A strengthened SDP relaxation for the maximum k-colorable subgraph problem yields tighter upper bounds than prior methods and is solvable in polynomial time on k-perfect graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a semidefinite programming relaxation for selecting the largest induced subgraph that admits a proper k-coloring. It introduces two new families of valid inequalities that tighten this relaxation, with one family recovering known inequalities for the Boolean quadric polytope when k equals one and the other generalizing rank inequalities from the stable-set problem. An alternating-direction-method-of-multipliers cutting-plane procedure solves the strengthened relaxation efficiently, producing upper bounds that exceed the best previously reported values across computational tests. The relaxation also admits properties that make the original problem polynomial-time solvable on the class of k-perfect graphs. The work further supplies an integer variant of the algorithm that returns high-quality feasible solutions via a binary semidefinite formulation.

Core claim

The authors consider the natural SDP relaxation of the maximum k-colorable subgraph problem and treat its optimum as a graph parameter. They derive two families of valid inequalities for the integer hull: the first reduces to a family for the Boolean quadric polytope at k=1, while the second generalizes the rank inequalities known for binary formulations of the stable-set problem. These inequalities are incorporated into a cutting-plane algorithm based on the alternating direction method of multipliers, which computes strengthened upper bounds that outperform the best existing bounds in the literature. The same relaxation possesses properties implying that the maximum k-colorable subgraph is

What carries the argument

The SDP relaxation of the maximum k-colorable subgraph problem, strengthened by two families of valid inequalities and solved via an ADMM-based cutting-plane procedure.

If this is right

  • The maximum k-colorable subgraph problem is solvable in polynomial time for every k-perfect graph.
  • The strengthened SDP relaxation produces upper bounds strictly better than the best previously published upper bounds on a wide range of test instances.
  • An integer ADMM procedure built on a binary SDP formulation returns high-quality feasible solutions for the same problem.
  • The cutting-plane method based on ADMM converges in practice to the strengthened SDP optimum.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same strengthening technique may be portable to SDP relaxations of related induced-subgraph problems such as maximum induced matching or maximum induced forest.
  • If the new bounds prove tight on additional graph families beyond k-perfect graphs, exact polynomial-time algorithms could exist for those families as well.
  • The first reported use of ADMM to recover integer solutions from a binary SDP model suggests the method could be tested on other combinatorial problems that admit similar formulations.

Load-bearing premise

The two new families of inequalities remain valid for every integer solution to the maximum k-colorable subgraph formulation.

What would settle it

Any graph together with a k-colorable induced subgraph whose size strictly exceeds the optimum value returned by the strengthened SDP relaxation.

Figures

Figures reproduced from arXiv: 2605.02456 by Mathijs Barkel, Renata Sotirov.

Figure 1
Figure 1. Figure 1: Effect of valid inequalities on the obtained upper bounds. view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper studies the maximum k-colorable subgraph (MkCS) problem via an SDP relaxation whose optimum is treated as a graph parameter. Properties of this parameter are shown to imply that MkCS is solvable in polynomial time on k-perfect graphs. Two new families of valid inequalities are derived to strengthen the relaxation: the first reduces to Boolean quadric inequalities when k=1, while the second generalizes rank inequalities from the stable-set formulation. The strengthened SDP is solved by an ADMM cutting-plane algorithm; extensive experiments indicate that the resulting upper bounds improve on the best known bounds in the literature. An integer ADMM variant based on a binary SDP formulation is also proposed to generate high-quality feasible solutions.

Significance. If the validity of the new inequalities and the stated properties of the SDP parameter hold, the work supplies both a theoretical classification result (polynomial-time solvability on k-perfect graphs) and practical improvements to bounding techniques for an NP-hard problem. The explicit generalization of known polyhedral inequalities and the application of ADMM to both the continuous relaxation and an integer formulation are concrete strengths.

major comments (3)
  1. [§3] §3: the claim that MkCS is solvable in polynomial time for k-perfect graphs rests on several properties of the SDP parameter; an explicit reduction or algorithm that uses these properties to obtain a polynomial-time procedure should be supplied.
  2. [§4] §4: the two families of valid inequalities are asserted to be valid for the integer hull of the MkCS formulation; a self-contained proof (or at least the key algebraic steps) for each family, including the explicit reduction of the first family to the Boolean quadric polytope when k=1, is needed to verify the central strengthening claim.
  3. [§5 and §6] §5 and §6: the ADMM cutting-plane procedure and the reported computational improvements are load-bearing for the practical contribution; convergence criteria, parameter choices, and complete numerical tables (not only summary statistics) should be provided to allow independent verification that the bounds are reliably stronger than those in the literature.
minor comments (2)
  1. [Notation and preliminaries] The notation for the SDP variable and the graph parameter should be introduced once and used consistently; occasional re-definition of symbols slows reading.
  2. [Figures] Figure captions could be expanded to state what is being plotted (e.g., bound gap versus instance size) rather than only the figure number.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and positive recommendation for minor revision. We address each of the major comments below and plan to incorporate the necessary additions in the revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3: the claim that MkCS is solvable in polynomial time for k-perfect graphs rests on several properties of the SDP parameter; an explicit reduction or algorithm that uses these properties to obtain a polynomial-time procedure should be supplied.

    Authors: We concur that an explicit procedure would enhance clarity. In the revised manuscript, we will supply a detailed description of the polynomial-time algorithm for the MkCS problem on k-perfect graphs. This will explicitly show how the properties of the SDP parameter (such as equality to the optimal value and other listed properties) can be used to compute the solution via solving the SDP and additional polynomial-time steps. revision: yes

  2. Referee: [§4] §4: the two families of valid inequalities are asserted to be valid for the integer hull of the MkCS formulation; a self-contained proof (or at least the key algebraic steps) for each family, including the explicit reduction of the first family to the Boolean quadric polytope when k=1, is needed to verify the central strengthening claim.

    Authors: We agree that self-contained proofs are essential. The revised paper will include complete proofs for the validity of both families of inequalities for the integer hull. For the first family, we will detail the algebraic reduction to the Boolean quadric polytope for k=1 by appropriate substitution of variables and showing that the inequalities match known valid inequalities. Key steps for the second family, generalizing rank inequalities, will also be provided. revision: yes

  3. Referee: [§5 and §6] §5 and §6: the ADMM cutting-plane procedure and the reported computational improvements are load-bearing for the practical contribution; convergence criteria, parameter choices, and complete numerical tables (not only summary statistics) should be provided to allow independent verification that the bounds are reliably stronger than those in the literature.

    Authors: We recognize the importance of reproducibility. In the revision, we will add a subsection detailing the convergence criteria (e.g., tolerance thresholds) and all parameter choices for the ADMM cutting-plane algorithm. Furthermore, we will provide complete numerical tables in the supplementary material or an appendix, listing the upper bounds for each test instance along with comparisons to existing bounds from the literature. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper introduces an SDP relaxation for the MkCS problem and treats its value as a graph parameter. It derives properties of this parameter to conclude polynomial-time solvability on k-perfect graphs, and separately proves two families of valid inequalities (one reducing to the Boolean quadric case for k=1 and the other generalizing rank inequalities for the stable-set formulation). These steps rely on standard SDP theory and direct validity arguments for the integer hull rather than any fitted parameter, self-referential definition, or load-bearing self-citation. The ADMM cutting-plane procedure and integer variant are presented as practical solvers whose correctness rests on established convex-optimization convergence results, with computational experiments serving only as empirical support. No equation or claim reduces by construction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on the standard validity of SDP relaxations for quadratic formulations of graph problems and on the convergence properties of ADMM; no new free parameters or invented entities are introduced.

axioms (1)
  • domain assumption The base SDP relaxation provides a valid upper bound on the maximum k-colorable subgraph size
    Invoked when the strengthened formulation is presented as an improvement over the existing SDP bound

pith-pipeline@v0.9.0 · 5545 in / 1260 out tokens · 57993 ms · 2026-05-08T17:38:04.157694+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

56 extracted references · 56 canonical work pages

  1. [1]

    Alizadeh, F. (1995). Interior point methods in semidefinite programming with applications to combinatorial optimization.SIAM Journal on Optimization, 5(1):13–39

    work page 1995

  2. [2]

    Bentert, M., Bevern, R., and Niedermeier, R. (2019). Inductivek-independent graphs andc- colorable subgraphs in scheduling: A review.Journal of Scheduling, 22(1):3–20

    work page 2019

  3. [3]

    Berge, C. (1992). Theq-perfect graphs, II.Matematiche (Catania), 47:205–211

    work page 1992

  4. [4]

    Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers.Foundations and Trends in Machine Learning, 3:1–122

    work page 2011

  5. [5]

    Boyle, J. P. and Dykstra, R. L. (1986). A method for finding projections onto the intersection of convex sets in Hilbert spaces. In Dykstra, R., Robertson, T., and Wright, F. T., editors,Advances in Order Restricted Statistical Inference, pages 28–47. Springer, New York, NY

    work page 1986

  6. [6]

    and Kerbosch, J

    Bron, C. and Kerbosch, J. (1973). Algorithm 457: Finding all cliques of an undirected graph. Communications of the ACM, 16(9):575–577

    work page 1973

  7. [7]

    and Corrˆ ea, R

    Campˆ elo, M. and Corrˆ ea, R. C. (2010). A combined parallel Lagrangian decomposition and cutting- plane generation for maximum stable set problems.Electronic Notes in Discrete Mathematics, 36:503–510. ISCO 2010 - International Symposium on Combinatorial Optimization

    work page 2010

  8. [8]

    Carlisle, M. C. and Lloyd, E. L. (1995). On thek-coloring of intervals.Discrete Applied Mathe- matics, 59(3):225–235

    work page 1995

  9. [9]

    Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. (2006). The strong perfect graph theorem.Annals of Mathematics, 164(1):51–229. 27

    work page 2006

  10. [10]

    de Meijer, F., Siebenhofer, M., Sotirov, R., and Wiegele, A. (2025). Spanning and splitting: Integer semidefinite programming for the quadratic minimum spanning tree problem.European Journal of Operational Research, 331(2):381–395

    work page 2025

  11. [11]

    and Sotirov, R

    de Meijer, F. and Sotirov, R. (2021). SDP-based bounds for the quadratic cycle cover problem via cutting-plane augmented Lagrangian methods and reinforcement learning.INFORMS Journal on Computing, 33(4):1262–1276

    work page 2021

  12. [12]

    and Sotirov, R

    de Meijer, F. and Sotirov, R. (2024). On integrality in semidefinite programming for discrete optimization.SIAM Journal on Optimization, 34(1):1071–1096

    work page 2024

  13. [13]

    de Meijer, F., Sotirov, R., Wiegele, A., and Zhao, S. (2023). Partitioning through projec- tions: Strong SDP bounds for large graph partition problems.Computers & Operations Research, 151:106088

    work page 2023

  14. [14]

    and Rendl, F

    Dukanovic, I. and Rendl, F. (2007). Semidefinite programming relaxations for graph coloring and maximal clique problems.Mathematical Programming, 109:345–365

    work page 2007

  15. [15]

    and Mahjoub, A

    Fouilhoux, P. and Mahjoub, A. R. (2012). Solving VLSI design and DNA sequencing problems using bipartization of graphs.Computational Optimization and Applications, 51(2):749–781

    work page 2012

  16. [16]

    and Rendl, F

    Gaar, E. and Rendl, F. (2020). A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring.Mathematical Programming, 183:283–308

    work page 2020

  17. [17]

    and Boyd, S

    Grant, M. and Boyd, S. (2014). CVX: Matlab software for disciplined convex programming, version 2.1.https://cvxr.com/cvx

    work page 2014

  18. [18]

    Greene, C. (1976). Some partitions associated with a partially ordered set.Journal of Combina- torial Theory, Series A, 20(1):69–79

    work page 1976

  19. [19]

    and Kleitman, D

    Greene, C. and Kleitman, D. J. (1976). The structure of Spernerk-families.Journal of Combi- natorial Theory, Series A, 20(1):41–68

    work page 1976

  20. [20]

    Gr¨ otschel, M., Lov´ asz, L., and Schrijver, A. (1984). Polynomial algorithms for perfect graphs. Annals of discrete mathematics, 88:325–356

    work page 1984

  21. [21]

    and Rendl, F

    Gruber, G. and Rendl, F. (2003). Computational experience with stable set relaxations.SIAM Journal on Optimization, 13(4):1014–1028

    work page 2003

  22. [22]

    Halld´ orsson, M., Li, L., Halpern, J., and Mirrokni, V. (2004). On spectrum sharing games. Distributed Computing, 22(4):235–248

    work page 2004

  23. [23]

    He, B., Ma, F., and Yuan, X. (2016). Convergence study on the symmetric version of ADMM with larger step sizes.SIAM Journal on Imaging Sciences, 9(3):1467–1501

    work page 2016

  24. [24]

    (2000).Semidefinite Programming for Combinatorial Optimization

    Helmberg, C. (2000).Semidefinite Programming for Combinatorial Optimization. Konrad-Zuse- Zentrum f¨ ur Informationstechnik, Berlin

    work page 2000

  25. [25]

    Hertz, A., Montagn´ e, R., and Gagnon, F. (2016). Constructive algorithms for the partial directed weighted improper coloring problem.Journal of Graph Algorithms and Applications, 20(2):159–188

    work page 2016

  26. [26]

    and Sotirov, R

    Hu, H. and Sotirov, R. (2020). On solving the quadratic shortest path problem.INFORMS Journal on Computing, 32(2):219–233

    work page 2020

  27. [27]

    and Pfetsch, M

    Januschowski, T. and Pfetsch, M. E. (2011a). Branch-cut-and-propagate for the maximum k- colorable subgraph problem with symmetry. In Achterberg, T. and Beck, J. C., editors,Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 99–116. Springer, Berlin, Heidelberg. 28

    work page

  28. [28]

    and Pfetsch, M

    Januschowski, T. and Pfetsch, M. E. (2011b). The maximumk-colorable subgraph problem and orbitopes.Discrete Optimization, 8(3):478–494

    work page

  29. [29]

    (2021).l 2-box ADMM decoding for LDPC codes over ISI channels.IEEE Transactions on Vehicular Technology, 70(4):3966–3971

    Jiao, X., Liu, H., Mu, J., and He, Y.-C. (2021).l 2-box ADMM decoding for LDPC codes over ISI channels.IEEE Transactions on Vehicular Technology, 70(4):3966–3971

    work page 2021

  30. [30]

    S., Mehrotra, A., and Trick, M

    Johnson, D. S., Mehrotra, A., and Trick, M. A. (2002). COLOR02/03/04: Graph coloring and its generalizations.https://mat.tepper.cmu.edu/COLOR04

    work page 2002

  31. [31]

    Johnson, D. S. and Trick, M. A. (1996).Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. AMS, Boston, MA

    work page 1996

  32. [32]

    and Scheffel, M

    Koster, A. and Scheffel, M. (2007). A routing and network dimensioning strategy to reduce wavelength continuity conflicts in all-optical networks. InProceedings of the International Network Optimization Conference (INOC) 2007

    work page 2007

  33. [33]

    Kuryatnikova, O., Sotirov, R., and Vera, J. C. (2022). The maximumk-colorable subgraph problem and related problems.INFORMS Journal on Computing, 34(1):656–669

    work page 2022

  34. [34]

    N., Rossi, F., and Smriglio, S

    Letchford, A. N., Rossi, F., and Smriglio, S. (2020). The stable set problem: Clique and nodal inequalities revisited.Computers & Operations Research, 123:105024

    work page 2020

  35. [35]

    Letchford, A. N. and Sørensen, M. (2012). Binary positive semidefinite matrices and associated integer polytopes.Mathematical Programming, 131:253–271

    work page 2012

  36. [36]

    Lewis, J. M. and Yannakakis, M. (1980). The node-deletion problem for hereditary properties is NP-complete.Journal of Computer and System Sciences, 20(2):219–230

    work page 1980

  37. [37]

    K., Sun, H., and Wolkowicz, H

    Li, X., Pong, T. K., Sun, H., and Wolkowicz, H. (2021). A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem.Computational Optimization and Applications, 78:853–891

    work page 2021

  38. [38]

    Lippert, R., Schwartz, R., Lancia, G., and Istrail, S. (2002). Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem.Briefings in bioinformatics, 3(1):23–31

    work page 2002

  39. [39]

    Lov´ asz, L. (1979). On the Shannon capacity of a graph.Information Theory, IEEE Transactions on, 25:1–7

    work page 1979

  40. [40]

    Lov´ asz, L. (1983). Perfect graphs. In Beineke, L. W. and Wilson, R. J., editors,Selected Topics in Graph Theory II, pages 55–87. Academic Press

    work page 1983

  41. [41]

    Marek-Sadowska, M. (1984). An unconstrained topological via minimization problem for two- layer routing.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 3(3):184–190

    work page 1984

  42. [42]

    W., Olkin, I., and Arnold, B

    Marshall, A. W., Olkin, I., and Arnold, B. C. (2011).Inequalities: Theory of majorization and its applications. Springer, New York, NY

    work page 2011

  43. [43]

    (1989).The maximumk-colorable subgraph problem

    Narasimhan, G. (1989).The maximumk-colorable subgraph problem. PhD thesis, University of Wisconsin-Madison

    work page 1989

  44. [44]

    and Manber, R

    Narasimhan, G. and Manber, R. (1990). A generalization of Lov´ aszϑfunction.DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1:19–27

    work page 1990

  45. [45]

    Nemhauser, G. L. and Trotter, L. E. (1974). Properties of vertex packing and independence system polyhedra.Mathematical Programming, 6(1):48–61

    work page 1974

  46. [46]

    E., Wolkowicz, H., and Xu, Y

    Oliveira, D. E., Wolkowicz, H., and Xu, Y. (2018). ADMM for the SDP relaxation of the QAP. Mathematical Programming Computation, 10:631–658. 29

    work page 2018

  47. [47]

    Oliveira, T. L. (2024). The maximumk-colorable subgraph problem. Master thesis, Universidade de S˜ ao Paulo

    work page 2024

  48. [48]

    Padberg, M. (1989). The Boolean quadric polytope: Some characteristics, facets and relatives. Mathematical Programming, 45(1):139–172

    work page 1989

  49. [49]

    and Rendl, F

    Pucher, D. and Rendl, F. (2023). Stable-set and coloring bounds based on 0-1 quadratic opti- mization.Applied Set-Valued Analysis and Optimization, 5(2):233–251

    work page 2023

  50. [51]

    Quintero, R., Bernal, D., Terlaky, T., and Zuluaga, L. F. (2022). Characterization of QUBO reformulations for the maximumk-colorable subgraph problem.Quantum Information Processing, 21:89

    work page 2022

  51. [52]

    Schrijver, A. (1979). A comparison of the Delsarte and Lov´ asz bounds.IEEE Transactions on Information Theory, 25(4):425–429

    work page 1979

  52. [53]

    and Sotirov, R

    Sinjorgo, L. and Sotirov, R. (2022). On the generalizedϑ-number and related problems for highly symmetric graphs.SIAM Journal on Optimization, 32(2):1344–1378

    work page 2022

  53. [54]

    Sinjorgo, L., Sotirov, R., and Vera, J. C. (2025). SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy. Preprint,https://arxiv.org/abs/2506.08648

    work page arXiv 2025

  54. [55]

    P., Gupta, H., Das, S

    Subramanian, A. P., Gupta, H., Das, S. R., and Buddhikot, M. M. (2007). Fast spectrum allocation in coordinated dynamic spectrum access based cellular networks. In2007 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks, pages 320–330

    work page 2007

  55. [56]

    and Ghanem, B

    Wu, B. and Ghanem, B. (2019).ℓ p-box ADMM: A versatile framework for integer programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(7):1695–1708

    work page 2019

  56. [57]

    Wu, Q., Zhang, F., Wang, H., Lin, J., and Liu, Y. (2018). Parameter-freeℓ p-box decoding of LDPC codes.IEEE Communications Letters, 22(7):1318–1321. Statements and declarations FundingThe authors declare that no funds, grants, or other support were received during the preparation of this manuscript. Competing interestsThe authors have no relevant financia...

    work page arXiv 2018