pith. sign in

arxiv: 2606.09509 · v1 · pith:3PMVAYF4new · submitted 2026-06-08 · 💻 cs.NE

Local Search on Vertex Coloring for Bipartite Graphs

Johanna Gasse This is my paper

Pith reviewed 2026-06-27 14:18 UTC · model grok-4.3

classification 💻 cs.NE
keywords local searchvertex coloringbipartite graphsmutation operatorruntime analysisgray-box optimization
0
0 comments X

The pith

A gray-box local search mutation operator finds optimal vertex colorings on complete bipartite graphs in expected Θ(n log n) time.

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

The paper studies local search for the vertex coloring problem on bipartite graphs. It first shows that on general bipartite graphs, local optima that are arbitrarily far from the global optimum can exist, so local search can return arbitrarily bad colorings. On complete bipartite graphs the paper introduces a gray-box mutation operator that removes less frequent colors with higher probability and proves that this operator reaches an optimal 2-coloring in expected Θ(n log n) time. This bound is a drastic improvement over the exponential expected runtime of black-box random local search on the same graphs.

Core claim

The paper proves that a gray-box local search mutation operator which removes less frequent colors with higher probability finds an optimal coloring on complete bipartite graphs in an expected runtime of Θ(n log n). This is established by analyzing the local search landscape on complete bipartite graphs and showing that the biased mutation drives the process to the global optimum at the stated rate.

What carries the argument

The gray-box local search mutation operator that removes less frequent colors with higher probability.

If this is right

  • On complete bipartite graphs the gray-box operator reaches the global optimum while black-box random local search requires exponential time.
  • General bipartite graphs admit local optima that use arbitrarily many colors beyond the chromatic number.
  • Local search landscapes on bipartite graphs can contain only global optima or can contain non-global local optima depending on the graph structure.
  • Gray-box information about color frequencies suffices to obtain a polynomial expected runtime on complete bipartite graphs.

Where Pith is reading between the lines

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

  • The same frequency-biased mutation might be tested on other graph classes that admit efficient 2-colorings but contain local-search traps.
  • The Θ(n log n) bound likely arises from a coupon-collector-like process over the color classes and could be verified by direct simulation on small complete bipartite graphs.
  • If the bias toward rare colors is removed, the expected runtime on complete bipartite graphs reverts to the exponential black-box bound shown in the paper.

Load-bearing premise

The runtime bound and optimality guarantee are proven only for complete bipartite graphs.

What would settle it

An experiment on a complete bipartite graph K_{n,n} in which the gray-box local search fails to reach a proper 2-coloring with high probability after O(n log n) steps.

Figures

Figures reproduced from arXiv: 2606.09509 by Johanna Gasse.

Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p030_3.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p031_3.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p032_3.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p033_3.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p034_3.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p037_4.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p038_4.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p046_4.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p047_4.png] view at source ↗
read the original abstract

Local search is a well-known heuristic method used in optimization. In this thesis, we explore its capabilities on the vertex coloring problem, an $NP$-hard problem with relevance in both theoretical analysis and practical application. To recognize limitations in the applicability of local search of the vertex coloring problem, we analyze local search landscapes on differently-structured bipartite graphs. We identify structures that ensure only global optima can exist as well as ones that enable the existence of non-global local optima, showing that on general bipartite graphs, it is possible for local search to return arbitrarily bad results. Further, we analyze the capabilities of local search on graphs where a local optimum can be found. To do so, we introduce a gray-box local search mutation operator that removes less frequent colors with higher probability and prove that it finds an optimal coloring on complete bipartite graphs in an expected run time of $\Theta(n \log n)$. This is a drastic improvement to the exponential tun time of the black-box Random Local Search, showing that gray-box mutation operators can improve the run time of local search.

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

1 major / 1 minor

Summary. The manuscript examines local search for vertex coloring on bipartite graphs. It shows that general bipartite graphs can have non-global local optima that local search may reach, leading to arbitrarily bad colorings. It introduces a gray-box mutation operator that removes less frequent colors with higher probability and proves that on complete bipartite graphs, this operator achieves an optimal coloring in expected Θ(n log n) time, a significant improvement over the exponential time of black-box random local search.

Significance. If the proof is correct, the work is significant in demonstrating the potential of gray-box information in local search to achieve near-linear expected runtime on structured instances like complete bipartite graphs. It also provides insight into the local search landscape for bipartite graphs, distinguishing cases where local optima are only global from those with bad local optima.

major comments (1)
  1. Abstract: the central claim is a proof that the gray-box mutation operator yields expected runtime Θ(n log n) on complete bipartite graphs, but the derivation steps, probability calculations for the biased removal of less frequent colors, and handling of the mutation operator are not visible, preventing verification of the analysis.
minor comments (1)
  1. The abstract refers to 'this thesis,' suggesting the text may be excerpted from a larger document; ensure the manuscript is self-contained with consistent terminology and section numbering if submitted as a standalone paper.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review and the recommendation for major revision. We address the single major comment below.

read point-by-point responses

  1. Referee: Abstract: the central claim is a proof that the gray-box mutation operator yields expected runtime Θ(n log n) on complete bipartite graphs, but the derivation steps, probability calculations for the biased removal of less frequent colors, and handling of the mutation operator are not visible, preventing verification of the analysis.

    Authors: We agree that the abstract, as a concise summary, cannot contain the full derivation. The manuscript body presents the proof of the Θ(n log n) bound, including the biased removal probabilities and mutation operator analysis. However, to address the verifiability concern, we will revise the manuscript by expanding the relevant section(s) with more explicit step-by-step derivations, clearer probability calculations, and improved structuring of the mutation operator handling. We will also slightly expand the abstract to better indicate the main analytical approach without exceeding length limits. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces a gray-box mutation operator and proves a Θ(n log n) expected runtime bound specifically for complete bipartite graphs via standard expected-time analysis of the operator's bias toward less frequent colors. The derivation relies on the operator definition and graph structure rather than any fitted parameters, self-referential definitions, or load-bearing self-citations that reduce the result to its inputs by construction. The comparison to exponential runtime for black-box RLS is presented as a contrast, not as a derived quantity from the new result. No steps match the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the definition of the gray-box mutation operator and on standard probabilistic analysis of local-search runtimes; no fitted numerical parameters are introduced.

axioms (1)
  • standard math Standard properties of expected runtime analysis for randomized local search algorithms
    Invoked to establish the Θ(n log n) bound from the biased mutation probabilities.
invented entities (1)
  • Gray-box mutation operator no independent evidence
    purpose: Bias removal probability toward less frequent colors to accelerate convergence on complete bipartite graphs
    New operator introduced in the paper; no independent evidence outside the claimed proof is provided.

pith-pipeline@v0.9.1-grok · 5702 in / 1261 out tokens · 21122 ms · 2026-06-27T14:18:36.311230+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

36 extracted references · 25 canonical work pages · 1 internal anchor

  1. [1]

    , date =

    Musser, David R. , date =. Introspective. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2- langid =

    work page doi:10.1002/(sici)1097-024x(199708)27:8

  2. [2]

    Exponential

    Heinen, Antonia , month = aug, year =. Exponential

  3. [3]

    and Jacobs, David P

    Linear time self-stabilizing colorings , volume =. Information Processing Letters , author =. 2003 , keywords =. doi:10.1016/S0020-0190(03)00299-0 , abstract =

    work page doi:10.1016/s0020-0190(03)00299-0 2003

  4. [4]

    Chaitin, G. J. , month = jun, year =. Register allocation & spilling via graph coloring , isbn =. Proceedings of the 1982. doi:10.1145/800230.806984 , abstract =

    work page doi:10.1145/800230.806984 1982

  5. [5]

    2004 , note =

    Periodica Polytechnica Electrical Engineering (Archives) , author =. 2004 , note =

    2004

  6. [6]

    Hill-climbing

    Selman, Bart and Gomes, Carla P , year =. Hill-climbing. Encyclopedia of. doi:10.1002/0470018860.s00015 , keywords =

    work page doi:10.1002/0470018860.s00015

  7. [7]

    Analyzing

    Jansen, Thomas , month = jan, year =. Analyzing

  8. [8]

    Journal of the Operational Research Society , author =

    Statistical. Journal of the Operational Research Society , author =. 2004 , keywords =. doi:10.1057/palgrave.jors.2601611 , abstract =

    work page doi:10.1057/palgrave.jors.2601611 2004

  9. [9]

    Variable

    Hansen, Pierre and Mladenović, Nenad , editor =. Variable. Handbook of. 2018 , doi =

    2018

  10. [10]

    Approximation

    Korte, Bernhard and Vygen, Jens , editor =. Approximation. Combinatorial. 2018 , doi =

    2018

  11. [11]

    Colouring , url =

    Diestel, Reinhard , editor =. Colouring , url =. Graph. 2025 , doi =

    2025

  12. [12]

    and Kolen, A

    Crama, Y. and Kolen, A. W. J. and Pesch, E. J. , editor =. Local search in combinatorial optimization , url =. Artificial. 1995 , doi =

    1995

  13. [13]

    Metaheuristics , url =

    Voß, Stefan , year =. Metaheuristics , url =. Encyclopedia of. doi:10.1007/978-0-387-74759-0_367 , pages =

    work page doi:10.1007/978-0-387-74759-0_367

  14. [14]

    and Rajabi, Amirhossein , editor =

    Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Rajabi, Amirhossein , editor =. Escaping. Parallel. 2022 , doi =

    2022

  15. [15]

    Journal of Heuristics , author =

    Testing heuristics:. Journal of Heuristics , author =. 1995 , keywords =. doi:10.1007/BF02430364 , abstract =

    work page doi:10.1007/bf02430364 1995

  16. [16]

    Watson, Jean-Paul , editor =. An. Handbook of. 2010 , doi =

    2010

  17. [17]

    and Ranganathan, K

    Balakrishnan, R. and Ranganathan, K. , editor =. Graph. A. 2012 , doi =

    2012

  18. [18]

    ACM Trans

    Crossover for. ACM Trans. Evol. Learn. Optim. , author =. 2023 , pages =. doi:10.1145/3603629 , abstract =

    work page doi:10.1145/3603629 2023

  19. [19]

    Analysis of a gray-box operator for vertex cover , isbn =

    Baguley, Samuel and Friedrich, Tobias and Kötzing, Timo and Li, Xiaoyue and Pappik, Marcus and Zeif, Ziena , month = jul, year =. Analysis of a gray-box operator for vertex cover , url =. doi:10.1145/3512290.3528848 , abstract =

    work page doi:10.1145/3512290.3528848

  20. [20]

    Analysis of an

    Sudholt, Dirk and Zarges, Christine , editor =. Analysis of an. Algorithms and. 2010 , doi =

    2010

  21. [21]

    Crossover is provably essential for the

    Sudholt, Dirk , month = jun, year =. Crossover is provably essential for the. doi:10.1145/1068009.1068202 , abstract =

    work page doi:10.1145/1068009.1068202

  22. [22]

    Whitley, Darrell , month = jul, year =. Mk. doi:10.1145/2739480.2754809 , abstract =

    work page doi:10.1145/2739480.2754809

  23. [23]

    Algorithmica , author =

    Time. Algorithmica , author =. 2021 , keywords =. doi:10.1007/s00453-021-00838-3 , abstract =

    work page doi:10.1007/s00453-021-00838-3 2021

  24. [24]

    Probabilistic

    Doerr, Benjamin , year =. Probabilistic. doi:10.1007/978-3-030-29414-4_1 , note =

    work page doi:10.1007/978-3-030-29414-4_1

  25. [25]

    Theoretical Computer Science , author =

    First-hitting times under drift , volume =. Theoretical Computer Science , author =. 2019 , keywords =. doi:10.1016/j.tcs.2019.08.021 , abstract =

    work page doi:10.1016/j.tcs.2019.08.021 2019

  26. [26]

    ICAPS , author =

    Mixed. ICAPS , author =. 2019 , pages =. doi:10.1609/icaps.v29i1.3521 , abstract =

    work page doi:10.1609/icaps.v29i1.3521 2019

  27. [27]

    Theory of

    Kötzing, Timo , month = jun, year =. Theory of. doi:10.48550/arXiv.2406.14589 , abstract =

    work page doi:10.48550/arxiv.2406.14589

  28. [28]

    Multiplicative drift analysis , url =

    Doerr, Benjamin and Johannsen, Daniel and Winzen, Carola , month = jul, year =. Multiplicative drift analysis , url =. doi:10.1145/1830483.1830748 , abstract =

    work page doi:10.1145/1830483.1830748

  29. [29]

    Oliveto and Carsten Witt

    Simplified. Algorithmica , author =. 2011 , keywords =. doi:10.1007/s00453-010-9387-z , abstract =

    work page doi:10.1007/s00453-010-9387-z 2011

  30. [30]

    Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

    Oliveto, Pietro S. and Witt, Carsten , month = nov, year =. Erratum:. doi:10.48550/arXiv.1211.7184 , abstract =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1211.7184

  31. [31]

    Jensen, J. L. W. V. , month = nov, year =. Sur les fonctions convexes et les inégualités entre les valeurs. doi:10.1007/bf02418571 , abstract =

    work page doi:10.1007/bf02418571

  32. [32]

    and Khuri, S

    Back, T. and Khuri, S. , booktitle=. An evolutionary heuristic for the maximum independent set problem , year=. doi:10.1109/ICEC.1994.350004 , ISSN=

    work page doi:10.1109/icec.1994.350004 1994

  33. [33]

    Randomized local search, evolutionary algorithms, and the minimum spanning tree problem , volume =

    Randomized local search, evolutionary algorithms, and the minimum spanning tree problem , volume =. Theoretical Computer Science , author =. 2007 , keywords =. doi:10.1016/j.tcs.2006.11.002 , abstract =

    work page doi:10.1016/j.tcs.2006.11.002 2007

  34. [34]

    Algorithmica , author =

    Static and. Algorithmica , author =. 2018 , keywords =. doi:10.1007/s00453-017-0341-1 , abstract =

    work page doi:10.1007/s00453-017-0341-1 2018

  35. [35]

    , month = sep, year =

    Branson, Luke and Sutton, Andrew M. , month = sep, year =. Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems , url =. doi:10.1145/3450218.3477304 , abstract =

    work page doi:10.1145/3450218.3477304

  36. [36]

    Systems, Man, and Cybernetics , author =

    A. Systems, Man, and Cybernetics , author =. 2005 , file =. doi:10.1109/TSMCC.2004.841903 , abstract =

    work page doi:10.1109/tsmcc.2004.841903 2005