pith. sign in

arxiv: 1906.10078 · v2 · pith:D3ZPFTVAnew · submitted 2019-06-24 · 💻 cs.CC · cs.DM

Finding Optimal Solutions With Neighborly Help

Elisabet Burjons , Fabian Frei , Edith Hemaspaandra , Dennis Komm , David Wehner This is my paper

Pith reviewed 2026-05-25 16:38 UTC · model grok-4.3

classification 💻 cs.CC cs.DM
keywords graph coloringvertex coverNP-hardnesscritical graphsminimality problemsDP-completenessTheta_2^p-completenessneighboring instances
0
0 comments X

The pith

Optimal graph colorings are NP-hard to recover from optimal colorings of all one-vertex-deleted subgraphs, even when one-edge-deleted solutions are also supplied.

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

The paper examines whether optimal solutions to NP-hard problems can be computed efficiently when given optimal solutions to neighboring instances that differ by one vertex or edge. For graph coloring it proves NP-hardness when the neighbors are obtained by vertex deletions or edge deletions, yet shows that two or more edge-addition supergraphs suffice for a polynomial-time algorithm. Vertex Cover behaves differently under the same neighbor model, which the authors use to separate the two problems structurally. Additional results establish that recognizing certain critical graphs is complete for DP or for Theta_2^p.

Core claim

It is NP-hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P. Vertex Cover exhibits a remarkably different behavior. Recognizing beta-vertex-critical graphs for Vertex Cover is Theta_2^p-complete, and Minimal-3-UnColorability is DP-complete.

What carries the argument

The neighborly-help model that supplies optimal solutions on all one-vertex-deleted, one-edge-deleted, or one-edge-added neighboring instances as additional input to the original instance.

If this is right

  • Coloring remains hard even when both vertex-deletion and edge-deletion neighbors are supplied.
  • Edge-addition neighbors make optimal coloring polynomial-time computable.
  • Vertex Cover and Coloring separate sharply under the neighbor model.
  • Minimal-3-UnColorability is DP-complete and beta-vertex-critical Vertex Cover is Theta_2^p-complete.

Where Pith is reading between the lines

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

  • The neighbor model could be used to classify other NP-hard problems by how much local information they require.
  • Edge addition appears to convey more structural information than deletion for coloring.
  • Similar neighbor queries might be studied for approximation or for average-case inputs.

Load-bearing premise

The supplied neighboring optimal solutions are exact and error-free.

What would settle it

A polynomial-time algorithm that outputs an optimal coloring given the optimal colorings of every one-vertex-deleted subgraph would falsify the NP-hardness result.

Figures

Figures reproduced from arXiv: 1906.10078 by David Wehner, Dennis Komm, Edith Hemaspaandra, Elisabet Burjons, Fabian Frei.

Figure 1
Figure 1. Figure 1: The graph h(Φ) − {vc, vs} for a 3-CNF-formula with C1 = x1 ∨ xi ∨ xj and Cm = xj ∨ xn ∨ xn. see [PITH_FULL_IMAGE:figures/full_fig_p019_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Any k-coloring of G is also a k-coloring for G ∪ {u, x} or G ∪ {v, x} or both. If a coloring is optimal for G, then it is also optimal for G ∪ {u, x} or G ∪ {v, x}. The figure depicts only the induced subgraphs of {u, v, x}. colored T. Change the color of the a-vertex to C and that of the b-vertex to F. Now we can color the triangle. This results in a 3-coloring of g(Φ) − C, and it is easy to check that we… view at source ↗
Figure 3
Figure 3. Figure 3: An example of the construction that we use in Subcol (Algorithm 2) for a k-colorable graph G, exploiting the fact that G is known to be universal-edged. In the example, we have k = 4. In general, the graph G is k-colorable if and only if the induced subgraph G[M] is (k − 2)-colorable. The subgraphs G[L] and G[R] are independent sets. The following relations hold in general as well: L = N(ℓ) − N[r] = V − N[… view at source ↗
read the original abstract

Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i.e., locally modified) instances? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems; most notably graph theory's core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, Colorability and Vertex Cover. For example, we show that it is NP-hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P. We observe that Vertex Cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For Vertex Cover, we show that recognizing beta-vertex-critical graphs is complete for Theta_2^p (parallel access to NP), obtaining the first completeness result for a criticality problem for this class.

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

0 major / 2 minor

Summary. The paper examines whether optimal solutions to NP-hard graph problems (primarily k-Colorability and Vertex Cover) can be computed in polynomial time from optimal solutions supplied for neighboring instances obtained by single-vertex deletions, single-edge deletions, or single-edge additions. It proves that optimal coloring cannot be recovered in polynomial time even when given optimal colorings of all one-vertex-deleted subgraphs (and remains NP-hard when one-edge-deleted subgraphs are also supplied), while recovery from one-edge-added supergraphs is in P (even from only two such supergraphs). Vertex Cover exhibits qualitatively different behavior. The paper also establishes that Minimal-3-UnColorability is DP-complete and that recognizing beta-vertex-critical graphs for Vertex Cover is Theta_2^p-complete.

Significance. If the stated reductions hold, the work supplies fine-grained structural distinctions among graph problems based on how their optima behave under local modifications and yields the first Theta_2^p-completeness result for a criticality problem as well as the first DP-completeness result for edge-deletion minimality in 3-colorability. These results strengthen the complexity-theoretic understanding of critical graphs and minimality problems.

minor comments (2)
  1. [Introduction] The abstract and introduction use the term 'beta-vertex-critical' without an explicit definition in the provided text; a one-sentence definition should appear at first use (likely in Section 1 or 2) to aid readers unfamiliar with the variant.
  2. [Abstract] The statement that recovery from two one-edge-added supergraphs is in P is asserted in the abstract; the precise algorithm or reduction establishing membership should be referenced by theorem number in the abstract or early in the introduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; results via standard reductions from known complete problems

full rationale

The paper establishes NP-hardness for computing optimal colorings from one-vertex- or one-edge-deleted neighbor optima, membership in P for one-edge-added supergraphs, DP-completeness for Minimal-3-UnColorability, and Theta_2^p-completeness for beta-vertex-critical Vertex Cover. All claims rest on polynomial-time reductions from established complete problems under the standard model where neighbor solutions are supplied exactly as input. No self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations appear; the derivation chain remains independent of the target results themselves.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies exclusively on the standard axioms of complexity theory (polynomial-time reductions, definitions of NP, DP, and Theta_2^p) with no free parameters, no invented entities, and no ad-hoc assumptions visible in the abstract.

axioms (1)
  • standard math Polynomial-time many-one reductions preserve membership in NP, DP, and Theta_2^p.
    Invoked implicitly by every hardness and completeness claim.

pith-pipeline@v0.9.0 · 5864 in / 1426 out tokens · 43942 ms · 2026-05-25T16:38:13.760114+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Reoptimizing the traveling salesman problem

    Claudia Archetti, Luca Bertazzi, and Maria Grazia Spera nza. Reoptimizing the traveling salesman problem. Networks, 42(3):154–159, 2003

    work page 2003

  2. [2]

    Reoptimization of minimum and maximum traveling salesman’s tours

    Giorgio Ausiello, Bruno Escoffier, Jérôme Monnot, and Van gelis Paschos. Reoptimization of minimum and maximum traveling salesman’s tours. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SW AT 2006), volume 4059 of Lecture Notes in Computer Science , pages 196–207. Springer-Verlag, 2006

    work page 2006

  3. [3]

    Reusing optimal TSP sol utions for locally modified input instances

    Hans-Joachim Böckenhauer, Luca Forlizzi, Juraj Hromko vič, Joachim Kneis, Joachim Kupke, Guido Proietti, and Peter Widmayer. Reusing optimal TSP sol utions for locally modified input instances. In Proceedings of the 4th IFIP International Conference on The oretical Computer Science (IFIP TCS 2006) , pages 251–270. Springer-Verlag, 2006

    work page 2006

  4. [4]

    Reoptimization of hard opti- mization problems

    Hans-Joachim Böckenhauer, Juraj Hromkovič, and Dennis Komm. Reoptimization of hard opti- mization problems. In Teofilo F. Gonzalez, editor, AAM Handbook of Approximation Algorithms and Metaheuristics , volume 1, chapter 25, pages 427–454. CRC Press 2018, 2nd edi tion, 2018

    work page 2018

  5. [5]

    On the hardness of reoptimization

    Hans-Joachim Böckenhauer, Juraj Hromkovič, Tobias Möm ke, and Peter Widmayer. On the hardness of reoptimization. In Proceedings of the 34th Conference on Current Trends in Theo ry and Practice of Computer Science (SOFSEM 2008) , volume 4910 of Lecture Notes in Computer Science, pages 50–65. Springer-Verlag, 2008

    work page 2008

  6. [6]

    Büning and Oliver Kullmann

    Hans K. Büning and Oliver Kullmann. Minimal unsatisfiabi lity and autarkies. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability 2009 , pages 339–401. IOS Press, 2009

    work page 2009

  7. [7]

    Jin-Yi Cai and Gabriele E. Meyer. Graph minimal uncolora bility is D P-complete. SIAM Journal on Computing , 16(2):259–277, 1987

    work page 1987

  8. [8]

    Gabriel A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, s3-2(1):69–81, 1952

    work page 1952

  9. [9]

    On the autored ucibility of functions

    Piotr Faliszewski and Mitsunori Ogihara. On the autored ucibility of functions. Theory of Com- puting Systems , 46(2):222–245, 2010

    work page 2010

  10. [10]

    Michael Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979

    work page 1979

  11. [11]

    Graph Theory

    Frank Harary. Graph Theory. Addison-Wesley, 1991

    work page 1991

  12. [12]

    The complexity of Kemeny elections

    Edith Hemaspaandra, Holger Spakowski, and Jörg Vogel. The complexity of Kemeny elections. Theoretical Computer Science , 349(3):382–391, 2005

    work page 2005

  13. [13]

    Entropy and Stability in Graphs

    Gwenaël Joret. Entropy and Stability in Graphs . PhD thesis, Université Libre de Bruxelles, Faculté des Sciences, 2008

    work page 2008

  14. [14]

    Meyer and Mike Paterson

    Albert R. Meyer and Mike Paterson. With what frequency a re apparently intractable problems difficult? Technical Report MIT/LCS/TM-126, Laboratory for Computer Science, MIT, Cam- bridge, MA, 1979

    work page 1979

  15. [15]

    Papadimitriou and David Wolfe

    Christos H. Papadimitriou and David Wolfe. The complex ity of facets resolved. Journal of Computer and System Sciences , 37(1):2–13, 1988

    work page 1988

  16. [16]

    Completeness in the Boolea n Hierarchy

    Jörg Rothe and Tobias Riege. Completeness in the Boolea n Hierarchy. Journal of Universal Computer Science , 12(5):551–578, 2006. 12

    work page 2006

  17. [17]

    Optimal algorithms for self-red ucible problems

    Claus-Peter Schnorr. Optimal algorithms for self-red ucible problems. In Proceedings of the 3rd International Colloquium on Automata, Languages, and Prog ramming, pages 322–337. Edinburgh University Press, 1976

    work page 1976

  18. [18]

    Schäffter

    Markus W. Schäffter. Scheduling with forbidden sets. Discrete Applied Mathematics, 72(1–2):155– 166, 1997

    work page 1997

  19. [19]

    Bounded query classes

    Karl Wagner. Bounded query classes. SIAM Journal on Computing , 19(5):833–846, 1990

    work page 1990

  20. [20]

    Klaus W. Wagner. More complicated questions about maxi ma and minima, and some closures of NP. Theoretical Computer Science , 51(1–2):53–80, 1987

    work page 1987

  21. [21]

    Criticity with respect to properties an d operations in graph theory

    Walter Wessel. Criticity with respect to properties an d operations in graph theory. In Lás- zló Lovász András Hajnal and Vera T. Sós, editors, Finite and Infinite Sets. (6th Hungarian Combinatorial Colloquium, Eger, 1981) , volume 2 of Colloquia Mathematica Societatis Janos Bolyai, pages 829–837. North-Holland, 1984. 13 A Tractability for Vertex Addition ...

    work page 1981

  22. [22]

    Color g(Φ) − C as explained above

    If e ={ xi, xi} , let C be a clause in f (Φ) such that xi occurs positively in C (note that it follows from the definition of f that every literal appears positively in at least one clause of f (Φ)). Color g(Φ) − C as explained above. If xi is colored F, change its color to T. This is still a 3-coloring of g(Φ) − C, and since xi occurs positively in C, we ...

    work page

  23. [23]

    Color g(Φ) − C as explained above

    If e ={ vc, ℓ i} , where ℓ i∈{ xi, xi} , let C be a clause in f (Φ) such that ℓ i occurs positively in C. Color g(Φ) − C as explained above. If ℓ i is colored T, then we can extend the coloring to a 3-coloring of g(Φ) in polynomial time. If ℓ i is colored F, change the color of ℓ i to C, and for every a-vertex connected to ℓ i, change its color from C to ...

    work page

  24. [24]

    Again, color g(Φ) − C as above

    Let C be a clause such that e is connected to a clause vertex of C. Again, color g(Φ) − C as above. If α satisfies f (Φ), we can in polynomial time compute a 3-coloring of g(Φ). So suppose that α does not satisfy f (Φ). Then all literal-vertices connected to a clause-verte x of C are colored F. When we try to extend this coloring, all a-vertices in the cla...

    work page