pith. sign in

arxiv: 2606.30298 · v1 · pith:TTWDXWIOnew · submitted 2026-06-29 · 💻 cs.DM

Convex Recoloring of General Graphs: Formulations, Polyhedra, and Computational Experiments

Boyue Lin , Phablo F. S. Moura , Roel Leus This is my paper

Pith reviewed 2026-06-30 02:56 UTC · model grok-4.3

classification 💻 cs.DM
keywords convex recoloringmixed-integer linear programmingbranch-and-cutgeneral graphspolyhedral comparisoncomputational experimentsconnected color classes
0
0 comments X

The pith

A representatives formulation solved by branch-and-cut outperforms three other MILP models for convex recoloring on general graphs.

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

The paper develops four mixed-integer linear programming formulations for the convex recoloring problem on general graphs, where each color class must induce a connected subgraph while minimizing the cost of vertices that change color. It compares the strength of the linear relaxations associated with each formulation through polyhedral analysis and then tests all four on benchmark instances plus newly generated synthetic instances. Computational results establish that the representatives formulation, embedded in a branch-and-cut framework, solves the largest number of instances to optimality and does so fastest overall. This provides the first systematic exact approach for the problem outside of trees.

Core claim

Among the four proposed MILP formulations for convex recoloring, the representatives model produces the strongest polytope under linear relaxation and, when solved by branch-and-cut, yields the best computational performance on both published benchmark instances and new synthetic test sets.

What carries the argument

The representatives formulation, which selects a representative vertex for each color class and enforces connectivity through assignment and linking constraints.

If this is right

  • The representatives formulation dominates the other three models on the tested instance classes.
  • Polyhedral comparisons correctly predict the relative strength observed in the branch-and-cut experiments.
  • Convex recoloring on general graphs is now amenable to exact solution on moderate-sized instances.
  • The new synthetic instance generator produces challenging test cases that differentiate the formulations.

Where Pith is reading between the lines

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

  • The same representatives modeling idea may transfer to other connectivity-constrained coloring problems on general graphs.
  • The synthetic instances could serve as a standardized testbed for future heuristic or approximation algorithms.
  • Lifting or strengthening the representatives inequalities might further improve the formulation without adding variables.

Load-bearing premise

The four MILP formulations are valid and correctly enforce that every color class induces a connected subgraph.

What would settle it

A collection of instances on which the representatives branch-and-cut either solves fewer problems to optimality or requires more time than the flow-based or other proposed formulations.

Figures

Figures reproduced from arXiv: 2606.30298 by Boyue Lin, Phablo F. S. Moura, Roel Leus.

Figure 1
Figure 1. Figure 1: Relationships among the LP relaxations of the four formulations. An arc ( [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Performance profiles and gaps for algorithm C without ( [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Performance profiles and gaps for the unweighted random instances. [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Performance profiles and gaps for the unweighted scale-free instances. [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Performance profiles and gaps for the weighted random instances. [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Performance profiles and gaps for the weighted scale-free instances. [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗
read the original abstract

A vertex coloring of a graph is convex if the vertices of each color induce a connected subgraph. In the convex recoloring problem (CR), the goal is to find a convex coloring while minimizing the weight of recolored vertices, i.e., vertices assigned a color different from their original one. This problem was originally motivated by the study of phylogenetic trees in bioinformatics and is NP-hard even on paths. Most existing research focuses on trees, with only limited results available for general graphs. We advance the state of the art by developing exact solution methods for CR on general graphs. In particular, we propose four mixed-integer linear programming formulations, including a compact flow-based model and a representatives model, and design corresponding solution methods. We compare the polytopes associated with the linear relaxation of the proposed formulations. Computational experiments on benchmark instances and on new synthetic instances show that a branch-and-cut algorithm based on the representatives formulation performs best overall.

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

2 major / 2 minor

Summary. The paper claims to advance exact methods for the convex recoloring problem on general graphs by proposing four MILP formulations (including a compact flow-based model and a representatives model), comparing the polytopes of their linear relaxations, and showing via computational experiments on benchmark and new synthetic instances that a branch-and-cut algorithm based on the representatives formulation performs best overall.

Significance. If the formulations are valid, the work is significant for extending convex recoloring methods from trees to general graphs. The polyhedral comparisons and identification of the strongest formulation provide useful guidance, and the inclusion of new synthetic instances plus reproducible experiments strengthens the empirical contribution.

major comments (2)
  1. [§3] §3 (formulations): the central claim that the four MILP models (flow-based, representatives, etc.) are valid for general graphs requires that their integer feasible solutions correspond exactly to convex colorings; the manuscript must explicitly argue or prove that the connectivity constraints forbid disconnected color classes on arbitrary graphs, as this is nontrivial and load-bearing for all subsequent polyhedral and computational claims.
  2. [§5, Table 4] §5 and Table 4 (computational results): the superiority of the representatives-based branch-and-cut is reported on benchmark and synthetic instances, but the instance generation rules, exclusion criteria, and whether all generated instances are reported must be detailed to confirm that the performance ranking is not affected by selective reporting or instance bias.
minor comments (2)
  1. [§2.1] §2.1: the definition of convex coloring could include a small illustrative example with a non-tree graph to clarify the connectivity requirement for readers.
  2. [Figure 2] Figure 2 (polytope diagram): labels or a table listing the number of variables and constraints for each formulation would improve clarity when comparing the models.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and recommendation of minor revision. We address each major comment below and will incorporate the requested clarifications and additions in the revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (formulations): the central claim that the four MILP models (flow-based, representatives, etc.) are valid for general graphs requires that their integer feasible solutions correspond exactly to convex colorings; the manuscript must explicitly argue or prove that the connectivity constraints forbid disconnected color classes on arbitrary graphs, as this is nontrivial and load-bearing for all subsequent polyhedral and computational claims.

    Authors: We agree that an explicit validity argument is necessary for general graphs. In the revised version we will insert a new subsection in §3 that proves, for each of the four formulations, that every integer feasible solution induces convex color classes and conversely. The argument proceeds by showing that the flow-conservation (or representative-path) constraints, together with the binary restrictions, enforce that each color class is connected; the proof does not rely on acyclicity and therefore holds for arbitrary graphs. revision: yes

  2. Referee: [§5, Table 4] §5 and Table 4 (computational results): the superiority of the representatives-based branch-and-cut is reported on benchmark and synthetic instances, but the instance generation rules, exclusion criteria, and whether all generated instances are reported must be detailed to confirm that the performance ranking is not affected by selective reporting or instance bias.

    Authors: We will expand the opening paragraphs of §5 with a complete description of the synthetic-instance generator (vertex counts, edge-probability ranges, color-assignment procedure, and seed values), the precise exclusion criteria applied (e.g., instances already convex or exceeding a preliminary feasibility check), and an explicit statement that every generated instance is included in the reported tables unless otherwise noted. The same level of detail will be added for the benchmark set. revision: yes

Circularity Check

0 steps flagged

No circularity in new MILP formulations and empirical evaluation

full rationale

The paper introduces four new MILP formulations (compact flow-based and representatives models) for convex recoloring on general graphs, compares their polytopes directly, and reports branch-and-cut performance on benchmark and synthetic instances. No self-citations, fitted parameters renamed as predictions, or self-definitional reductions appear; the central claims rest on the explicit construction of the models and independent computational results rather than any prior author work or input data.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are described in the abstract; the work relies on standard MILP modeling of connectivity constraints whose validity is assumed but not detailed here.

pith-pipeline@v0.9.1-grok · 5696 in / 1104 out tokens · 33551 ms · 2026-06-30T02:56:34.285772+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

59 extracted references · 2 canonical work pages

  1. [1]

    Mathematical Programming , note=

    On the connected (sub)partition polytope , author=. Mathematical Programming , note=. doi:10.1007/s10107-025-02321-1 , year=

    work page doi:10.1007/s10107-025-02321-1

  2. [2]

    Combining

    Rehfeldt, Daniel and Koch, Thorsten , journal=. Combining. 2019 , publisher=

    2019

  3. [3]

    2004 , author =

    Multiway cuts in node weighted graphs , journal =. 2004 , author =

    2004

  4. [4]

    Information Processing Letters , volume=

    Cliques, holes and the vertex coloring polytope , author=. Information Processing Letters , volume=. 2004 , publisher=

    2004

  5. [5]

    2013 , author =

    Polyhedral studies on the convex recoloring problem , journal =. 2013 , author =

    2013

  6. [6]

    The Rooted Maximum Node-Weight Connected Subgraph Problem

    \'A lvarez-Miranda, Eduardo and Ljubi \' c , Ivana and Mutzel, Petra. The Rooted Maximum Node-Weight Connected Subgraph Problem. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 2013

    2013

  7. [7]

    Facets of combinatorial optimization: Festschrift for Martin Gr

    The maximum weight connected subgraph problem , author=. Facets of combinatorial optimization: Festschrift for Martin Gr. 2013 , publisher=

    2013

  8. [8]

    and Freire, A

    Campêlo, M. and Freire, A. S. and Lima, K. R. and Moura, P. F. S. and Wakabayashi, Y. , title =. Mathematical Programming , volume =. 2016 , type =

    2016

  9. [9]

    and Freire, A

    Campêlo, M. and Freire, A. S. and Moura, P. F. S. and Soares, J. C. , title =. European Journal of Operational Research , volume =. 2022 , type =

    2022

  10. [10]

    and Filipecki, B

    Chopra, S. and Filipecki, B. and Lee, K. and Ryu, M. and Shim, S. and Van Vyve, M. , title =. Mathematical Programming , volume =. 2017 , type =

    2017

  11. [11]

    Ford, L. R. and D. R. Fulkerson. Notes on Linear Programming: Part XX Maximal Flow Through a Network. 1954

    1954

  12. [12]

    Computer scheduling of public transport urban passenger vehicle and crew scheduling , pages=

    An integer programming approach to scheduling , author=. Computer scheduling of public transport urban passenger vehicle and crew scheduling , pages=. 1981 , publisher=

    1981

  13. [13]

    Partial Convex Recolorings of Trees and Galled Networks: Tight Upper and Lower Bounds , volume =

    Moran, Shlomo and Snir, Sagi and Sung, Wing-Kin , year =. Partial Convex Recolorings of Trees and Galled Networks: Tight Upper and Lower Bounds , volume =

  14. [14]

    Discrete Applied Mathematics , volume=

    Minimizing phylogenetic number to find good evolutionary trees , author=. Discrete Applied Mathematics , volume=. 1996 , publisher=

    1996

  15. [15]

    and Maciel, Tarcisio F

    Campêlo, Manoel and Soares, Joel C. and Maciel, Tarcisio F. and Lima, F. Rafael M. , title =. International Transactions in Operational Research , volume =

  16. [16]

    International Computing and Combinatorics Conference , pages=

    Connected coloring completion for general graphs: Algorithms and complexity , author=. International Computing and Combinatorics Conference , pages=. 2007 , organization=

    2007

  17. [17]

    2012 , author =

    The complexity of minimum convex coloring , journal =. 2012 , author =

    2012

  18. [18]

    2008 , author =

    Convex recolorings of strings and trees: Definitions, hardness results and algorithms , journal =. 2008 , author =

    2008

  19. [19]

    Computing and Combinatorics: 15th Annual International Conference, COCOON 2009 Niagara Falls, NY, USA, July 13-15, 2009 Proceedings 15 , pages=

    Convex recoloring revisited: Complexity and exact algorithms , author=. Computing and Combinatorics: 15th Annual International Conference, COCOON 2009 Niagara Falls, NY, USA, July 13-15, 2009 Proceedings 15 , pages=. 2009 , organization=

    2009

  20. [20]

    International Transactions in Operational Research , volume=

    A heuristic for the convex recoloring problem in graphs , author=. International Transactions in Operational Research , volume=. 2022 , publisher=

    2022

  21. [21]

    Modeling and Optimization: Theory and Applications: MOPTA, Bethlehem, PA, USA, August 2016 Selected Contributions 16 , pages=

    Column generation approach to the convex recoloring problem on a tree , author=. Modeling and Optimization: Theory and Applications: MOPTA, Bethlehem, PA, USA, August 2016 Selected Contributions 16 , pages=. 2017 , organization=

    2016

  22. [22]

    Mathematical Programming , volume=

    On imposing connectivity constraints in integer programs , author=. Mathematical Programming , volume=. 2017 , publisher=

    2017

  23. [23]

    Operations Research , volume=

    Imposing connectivity constraints in forest planning models , author=. Operations Research , volume=. 2013 , publisher=

    2013

  24. [24]

    Nature Biotechnology , volume=

    Global protein function prediction from protein-protein interaction networks , author=. Nature Biotechnology , volume=. 2003 , publisher=

    2003

  25. [25]

    Nature Biotechnology , volume=

    A network of protein-protein interactions in yeast , author=. Nature Biotechnology , volume=. 2000 , publisher=

    2000

  26. [26]

    Modeling

    Calvert, Kenneth L and Doar, Matthew B and Zegura, Ellen W , journal=. Modeling. 1997 , publisher=

    1997

  27. [27]

    Zur allgemeinen

    Menger, Karl , journal=. Zur allgemeinen. 1927 , publisher=

    1927

  28. [28]

    Science , volume=

    Emergence of scaling in random networks , author=. Science , volume=. 1999 , publisher=

    1999

  29. [29]

    Nature Reviews Genetics , volume=

    Network biology: Understanding the cell's functional organization , author=. Nature Reviews Genetics , volume=. 2004 , publisher=

    2004

  30. [30]

    Automated experimentation , volume=

    Construction and analysis of protein--protein interaction networks , author=. Automated experimentation , volume=. 2010 , publisher=

    2010

  31. [31]

    Journal of Theoretical Biology , volume=

    Evolving protein interaction networks through gene duplication , author=. Journal of Theoretical Biology , volume=. 2003 , publisher=

    2003

  32. [32]

    Physica A: Statistical Mechanics and Its Applications , volume=

    Scale-free characteristics of random networks: The topology of the world-wide web , author=. Physica A: Statistical Mechanics and Its Applications , volume=. 2000 , publisher=

    2000

  33. [33]

    Physical Review E , volume=

    Epidemic dynamics in finite size scale-free networks , author=. Physical Review E , volume=. 2002 , publisher=

    2002

  34. [34]

    2011 , publisher=

    Graph Theory , author=. 2011 , publisher=

    2011

  35. [35]

    Electronic Notes in Theoretical Computer Science , volume=

    Dezs. Electronic Notes in Theoretical Computer Science , volume=. 2011 , publisher=

    2011

  36. [36]

    Mathematical Programming , volume=

    Benchmarking optimization software with performance profiles , author=. Mathematical Programming , volume=. 2002 , publisher=

    2002

  37. [37]

    Mathematical Programming , volume=

    The vertex separator problem: a polyhedral investigation , author=. Mathematical Programming , volume=. 2005 , publisher=

    2005

  38. [38]

    Bioinformatics , volume=

    Discovering regulatory and signalling circuits in molecular interaction networks , author=. Bioinformatics , volume=. 2002 , publisher=

    2002

  39. [39]

    2007 , author =

    Efficient approximation of convex recolorings , journal =. 2007 , author =

    2007

  40. [40]

    Theoretical Computer Science , volume=

    Hardness and inapproximability of convex recoloring problems , author=. Theoretical Computer Science , volume=. 2014 , publisher=

    2014

  41. [41]

    2018 , note =

    1.5-approximation algorithm for the 2-Convex Recoloring problem , journal =. 2018 , note =. doi:https://doi.org/10.1016/j.dam.2017.01.008 , url =

    work page doi:10.1016/j.dam.2017.01.008 2018

  42. [42]

    Discrete Applied Mathematics , volume=

    Strong intractability results for generalized convex recoloring problems , author=. Discrete Applied Mathematics , volume=. 2020 , publisher=

    2020

  43. [43]

    Discrete Applied Mathematics , volume=

    Convex recoloring of paths , author=. Discrete Applied Mathematics , volume=. 2014 , publisher=

    2014

  44. [44]

    Management Science , volume=

    Optimal political districting by implicit enumeration techniques , author=. Management Science , volume=. 1970 , publisher=

    1970

  45. [45]

    2012 IEEE Conference on Computer Vision and Pattern Recognition , pages=

    Efficient activity detection with max-subgraph search , author=. 2012 IEEE Conference on Computer Vision and Pattern Recognition , pages=. 2012 , organization=

    2012

  46. [46]

    CVPR 2011 , pages=

    Efficient region search for object detection , author=. CVPR 2011 , pages=. 2011 , organization=

    2011

  47. [47]

    Operations Research , volume=

    Imposing contiguity constraints in political districting models , author=. Operations Research , volume=. 2022 , publisher=

    2022

  48. [48]

    Discrete Applied Mathematics , volume=

    On the asymmetric representatives formulation for the vertex coloring problem , author=. Discrete Applied Mathematics , volume=. 2008 , publisher=

    2008

  49. [49]

    Mathematical Programming Computation , volume=

    Political districting to minimize cut edges , author=. Mathematical Programming Computation , volume=. 2022 , publisher=

    2022

  50. [50]

    INFORMS Journal on Computing , year=

    Branch-and-price for the set-union bin packing problem , author=. INFORMS Journal on Computing , year=

  51. [51]

    European Journal of Operational Research , year=

    Compact formulations and valid inequalities for parallel machine scheduling with conflicts , author=. European Journal of Operational Research , year=

  52. [52]

    Handbooks in Operations Research and Management Science , volume=

    Optimal trees , author=. Handbooks in Operations Research and Management Science , volume=. 1995 , publisher=

    1995

  53. [53]

    Scientific reports , volume=

    Ability paradox of cascading model based on betweenness , author=. Scientific reports , volume=. 2015 , publisher=

    2015

  54. [54]

    Nature , volume=

    Evidence for dynamically organized modularity in the yeast protein--protein interaction network , author=. Nature , volume=. 2004 , publisher=

    2004

  55. [55]

    BMC bioinformatics , volume=

    Essentiality and centrality in protein interaction networks revisited , author=. BMC bioinformatics , volume=. 2015 , publisher=

    2015

  56. [56]

    Thinning out

    Fischetti, Matteo and Leitner, Markus and Ljubi. Thinning out. Mathematical Programming Computation , volume=. 2017 , publisher=

    2017

  57. [57]

    European Journal of Operational Research , volume=

    Partitioning a graph into balanced connected classes: Formulations, separation and experiments , author=. European Journal of Operational Research , volume=. 2021 , publisher=

    2021

  58. [58]

    Nature , volume=

    Lethality and centrality in protein networks , author=. Nature , volume=. 2001 , publisher=

    2001

  59. [59]

    Ana P. S. Dantas and Cid C. de Souza and Zanoni Dias , title =. 2018 , url =

    2018