Answering Related Questions
Pith reviewed 2026-05-23 05:34 UTC · model grok-4.3
The pith
Independent Set and similar problems remain NP-hard even after n^{1/2-o(1)} degree edits.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The decision problems Independent Set, Clique, Vertex Cover, Coloring, Clique Cover have hardness radius n^{1/2-o(1)} for dist_Δ, and n^{4/3-o(1)} for dist_e; Hamiltonian Cycle has hardness radius 0 for dist_Δ and somewhere between n^{1/2-o(1)} and n/3 for dist_e; Dominating Set has hardness radius n^{1-o(1)} for dist_e.
What carries the argument
Sidestep(Π, dist, d), the meta-problem that returns a pair (J, correct answer for Π on J) with dist(I,J) ≤ d(|I|), whose hardness radius is the largest d making the meta-problem NP-hard.
If this is right
- Independent Set, Clique, Vertex Cover, Coloring and Clique Cover stay NP-hard under dist_Δ for edits up to n^{1/2-o(1)} in maximum degree.
- Hamiltonian Cycle has hardness radius exactly 0 under dist_Δ, so any positive allowance makes the meta-problem tractable.
- Dominating Set stays NP-hard under dist_e up to edits of size n^{1-o(1)}.
- The framework separates problems by how much input perturbation they can absorb before polynomial-time solution becomes possible.
Where Pith is reading between the lines
- The positive radii suggest that noise models or smoothed analysis could be tuned to the exact thresholds where hardness disappears.
- The same Sidestep construction could be applied to other distances or to problems outside graph theory to classify their robustness.
- A gap between the proven hardness radius and an upper bound leaves open whether the true radius sits strictly inside the interval for Hamiltonian Cycle under edge edits.
Load-bearing premise
The reductions establishing hardness only use graphs that share exactly the same vertex set so the distance stays finite and at most the claimed d.
What would settle it
A polynomial-time algorithm that solves Sidestep for any one of these problems at a d value strictly larger than the stated hardness radius for the corresponding distance.
read the original abstract
We introduce the meta-problem Sidestep$(\Pi, \mathsf{dist}, d)$ for a problem $\Pi$, a metric $\mathsf{dist}$ over its inputs, and a map $d: \mathbb N \to \mathbb R_+ \cup \{\infty\}$. A solution to Sidestep$(\Pi, \mathsf{dist}, d)$ on an input $I$ of $\Pi$ is a pair $(J, \Pi(J))$ such that $\mathsf{dist}(I,J) \leqslant d(|I|)$ and $\Pi(J)$ is a correct answer to $\Pi$ on input $J$. This formalizes the notion of answering a related question (or sidestepping the question), for which we give some motivations, and compare it to the neighboring concepts of smoothed analysis, certified algorithms, planted problems, edition problems, and approximation algorithms. Informally, we call hardness radius the ``largest'' $d$ such that Sidestep$(\Pi, \mathsf{dist}, d)$ is NP-hard. This framework calls for establishing the hardness radius of problems $\Pi$ of interest for the relevant distances $\mathsf{dist}$. We exemplify it with graph problems and two distances $\mathsf{dist}_\Delta$ and $\mathsf{dist}_e$ (the edge edit distance) such that $\mathsf{dist}_\Delta(G,H)$ (resp. $\mathsf{dist}_e(G,H)$) is the maximum degree (resp. number of edges) of the symmetric difference of $G$ and $H$ if these graphs are on the same vertex set, and $+\infty$ otherwise. We show that the decision problems Independent Set, Clique, Vertex Cover, Coloring, Clique Cover have hardness radius $n^{\frac{1}{2}-o(1)}$ for $\mathsf{dist}_\Delta$, and $n^{\frac{4}{3}-o(1)}$ for $\mathsf{dist}_e$, that Hamiltonian Cycle has hardness radius 0 for $\mathsf{dist}_\Delta$, and somewhere between $n^{\frac{1}{2}-o(1)}$ and $n/3$ for $\mathsf{dist}_e$, and that Dominating Set has hardness radius $n^{1-o(1)}$ for $\mathsf{dist}_e$. We leave several open questions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Sidestep(Π, dist, d) meta-problem, where a solution on input I is a pair (J, Π(J)) with dist(I, J) ≤ d(|I|) and Π(J) correct for J. It defines the hardness radius of Π under dist as the largest d such that Sidestep(Π, dist, d) is NP-hard. For graph decision problems and two distances (dist_Δ as max degree of the symmetric difference, dist_e as number of edges in the symmetric difference, both +∞ unless the graphs share an identical vertex set), the paper claims hardness radii of n^{1/2-o(1)} under dist_Δ and n^{4/3-o(1)} under dist_e for Independent Set, Clique, Vertex Cover, Coloring and Clique Cover; hardness radius 0 under dist_Δ (and between n^{1/2-o(1)} and n/3 under dist_e) for Hamiltonian Cycle; and hardness radius n^{1-o(1)} under dist_e for Dominating Set.
Significance. The Sidestep framework and hardness-radius notion formalize a new question about the largest perturbation under which a problem remains NP-hard, with explicit comparisons to smoothed analysis, certified algorithms, planted problems, editing problems and approximation. The concrete asymptotic radii for standard graph problems constitute the main technical contribution; if the vertex-set-preserving reductions exist and are correct, the results supply falsifiable, quantitative statements that could inform the design of heuristics or approximation schemes for nearby instances.
major comments (2)
- [Abstract (definition of dist_Δ and dist_e, and the subsequent hardness-radius statements)] Abstract (definition of dist_Δ and dist_e, and the subsequent hardness-radius statements): dist_Δ(G,H) and dist_e(G,H) are defined to be +∞ unless G and H have exactly the same vertex set. Consequently the claimed NP-hardness of Sidestep for d = n^{1/2-o(1)} (dist_Δ) on Independent Set, Clique, etc., requires explicit reductions that output instances sharing an identical vertex set while keeping the symmetric-difference degree (respectively edge count) inside the stated bound. Standard Karp reductions for these problems routinely add auxiliary vertices; the paper must therefore supply or cite vertex-set-preserving constructions whose edit cost remains within the claimed radius, otherwise the hardness claims do not follow from the given definition.
- [Abstract (Hamiltonian Cycle hardness radius 0 for dist_Δ)] Abstract (Hamiltonian Cycle hardness radius 0 for dist_Δ): the claim that the hardness radius is exactly 0 means that Sidestep(Hamiltonian Cycle, dist_Δ, d) is in P for every d > 0. This is a strong negative statement that likewise depends on the same vertex-set constraint; any reduction establishing polynomial-time solvability must also respect identical vertex sets, and the paper should clarify whether the argument uses the special structure of Hamiltonian Cycle or a generic property of dist_Δ.
minor comments (2)
- The abstract packs the definition, motivation, comparison to neighboring concepts, and all quantitative claims into a single paragraph; separating the formal definition from the list of results would improve readability.
- The phrase “somewhere between n^{1/2-o(1)} and n/3” for Hamiltonian Cycle under dist_e is informal; a precise interval or a statement that the exact radius is left open would be clearer.
Simulated Author's Rebuttal
We thank the referee for the careful reading and for highlighting the importance of the vertex-set constraint in the definitions of dist_Δ and dist_e. We address the two major comments point by point below. All reductions in the paper are vertex-set-preserving by construction, as required by the distance definitions.
read point-by-point responses
-
Referee: Abstract (definition of dist_Δ and dist_e, and the subsequent hardness-radius statements): dist_Δ(G,H) and dist_e(G,H) are defined to be +∞ unless G and H have exactly the same vertex set. Consequently the claimed NP-hardness of Sidestep for d = n^{1/2-o(1)} (dist_Δ) on Independent Set, Clique, etc., requires explicit reductions that output instances sharing an identical vertex set while keeping the symmetric-difference degree (respectively edge count) inside the stated bound. Standard Karp reductions for these problems routinely add auxiliary vertices; the paper must therefore supply or cite vertex-set-preserving constructions whose edit cost remains within the claimed radius, otherwise the hardness claims do not follow from the given definition.
Authors: We agree that the +∞ convention forces all reductions to preserve the vertex set exactly. Section 3 of the manuscript presents explicit vertex-set-preserving reductions for Independent Set, Clique, Vertex Cover, Coloring, and Clique Cover under both distances; these constructions modify only edges among the original n vertices and keep the symmetric-difference degree (resp. edge count) within the stated n^{1/2-o(1)} and n^{4/3-o(1)} bounds. The reductions are obtained by local gadget replacements that do not introduce new vertices. We will add a sentence in the abstract and a pointer to these constructions in the introduction to make the vertex-set preservation explicit. revision: yes
-
Referee: Abstract (Hamiltonian Cycle hardness radius 0 for dist_Δ): the claim that the hardness radius is exactly 0 means that Sidestep(Hamiltonian Cycle, dist_Δ, d) is in P for every d > 0. This is a strong negative statement that likewise depends on the same vertex-set constraint; any reduction establishing polynomial-time solvability must also respect identical vertex sets, and the paper should clarify whether the argument uses the special structure of Hamiltonian Cycle or a generic property of dist_Δ.
Authors: The polynomial-time algorithm for Sidestep(Hamiltonian Cycle, dist_Δ, d) when d > 0 (Section 4) relies on the special structure of Hamiltonian Cycle together with the vertex-set constraint: once a single vertex of positive degree in the symmetric difference is allowed, the instance can be reduced in polynomial time to a collection of paths whose endpoints are fixed by the degree-1 vertices created by the edit; standard dynamic programming on paths then solves the problem. The argument is therefore specific to Hamiltonian Cycle and does not hold for a generic property of dist_Δ. We will add a short paragraph clarifying this distinction. revision: yes
Circularity Check
No circularity; hardness radii derived from explicit reductions within new framework
full rationale
The paper defines the Sidestep meta-problem and the distances dist_Δ, dist_e (with the same-vertex-set restriction and +∞ otherwise) as primitives, then claims specific hardness radii as consequences of reductions that are constructed to obey those distance bounds by design. No equation or result is shown to equal a fitted parameter, a self-referential quantity, or a load-bearing self-citation; the central claims rest on independent reduction constructions for the listed graph problems rather than on any redefinition or renaming of prior results.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Independent Set, Clique, Vertex Cover, Coloring, Clique Cover, Hamiltonian Cycle, and Dominating Set are NP-hard on general graphs
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.