Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs

Eshwar Srinivasan; Ramesh Hariharasubramanian

arxiv: 2605.25724 · v1 · pith:V6SN5WMHnew · submitted 2026-05-25 · 💻 cs.DS · cs.DM· math.CO

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs

Eshwar Srinivasan , Ramesh Hariharasubramanian This is my paper

Pith reviewed 2026-06-29 19:34 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.CO

keywords hereditary graphsedge distanceweighted maximum cliqueweighted maximum independent setfixed-parameter tractableedge-apex graphsedge-add graphs

0 comments

The pith

Weighted maximum clique and independent set solvable in O*(2^k) time on graphs k edge modifications from a hereditary class G that solves them in polynomial time.

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

The paper establishes algorithms for the weighted maximum clique and weighted maximum independent set problems on two natural extensions of hereditary graph classes: those obtained by deleting or adding at most one edge. It then generalizes these to the G-edge distance parameter k, which counts the minimum total edge deletions and non-edge additions needed to reach the hereditary class G. When the two problems are polynomial-time solvable on G, the paper shows they become solvable in O*(2^k) time on any graph at distance k. The same bound holds when the distance is measured to the class of transitive graphs.

Core claim

WMCP and WMISP can be solved in O*(2^k) time on graphs whose G-edge distance is k, provided these problems admit polynomial-time algorithms within the class G. This extends earlier algorithmic characterizations of the single edge-apex and edge-add classes to the more general setting of k-edge-distant graphs, and the bound also holds for graphs whose transitive-edge distance is k.

What carries the argument

The G-edge distance ξ_G(G), the minimum number of edge deletions plus non-edge additions required to turn G into a member of the hereditary class G.

If this is right

The O*(2^k) bound applies to any hereditary class G that solves the problems in polynomial time.
The single-modification edge-apex and edge-add classes become the k=1 special cases.
WMCP and WMISP admit O*(2^k) algorithms on graphs whose transitive-edge distance equals k.

Where Pith is reading between the lines

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

The same parameterization could be checked for other problems known to be polynomial on certain hereditary classes, such as coloring on perfect graphs.
The distance definition might be adapted to count only deletions or only additions to obtain tighter bounds for specific classes.
The approach suggests testing whether vertex-deletion distance to G yields analogous FPT results for the same problems.

Load-bearing premise

The hereditary class G must admit polynomial-time algorithms for weighted maximum clique and weighted maximum independent set.

What would settle it

A hereditary class G on which WMCP is solvable in polynomial time, together with an explicit graph at G-edge distance 1 on which WMCP requires super-polynomial time, would falsify the claimed reduction.

read the original abstract

In this work, we investigate the algorithmic aspects of two natural extensions of hereditary classes: the edge-apex class and the edge-add class, recently introduced by Singh and Sivaraman. These are defined as the graph classes obtained by at most one edge deletion or one non-edge addition, respectively, from a hereditary class $\mathcal{G}$. Building on earlier results showing that both classes remain hereditary and admit finite forbidden induced subgraph characterizations whenever $\mathcal{G}$ does, we focus on the Weighted Maximum Clique Problem (WMCP) and the Weighted Maximum Independent Set Problem (WMISP). We first present algorithms for WMCP and WMISP on both the edge-apex and edge-add classes of hereditary graph classes. Extending this framework, we introduce the notion of the $\mathcal{G}$-edge distance of a graph $G$, denoted by $\xi_{\mathcal{G}}(G)$, which quantifies how far $G$ is from the class $\mathcal{G}$ in terms of the minimum number of edge deletions or non-edge additions needed to transform it into a member of $\mathcal{G}$. By parameterizing with respect to this distance, we show that both WMCP and WMISP can be solved in $O^*(2^k)$ time on graphs whose $\mathcal{G}$-edge distance is $k$, provided these problems admit polynomial-time algorithms within the class $\mathcal{G}$. This result extends earlier algorithmic characterizations of the single edge-apex and edge-add classes to the more general setting of $k$-edge-distant graphs. By combining our general results with known properties of transitive graphs, we show that WMCP and WMISP can be solved in $O^*(2^k)$ time for graphs with transitive-edge distance $k$.

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.

Desk Editor's Note private letter to a colleague

The paper claims an O*(2^k) lift for weighted clique and independent set from any hereditary base class G to graphs at G-edge distance k, but the single-exponential bound is the part that needs verification.

read the letter

The core result is that if weighted max clique and independent set are polynomial-time solvable on a hereditary class G, then both problems are solvable in O*(2^k) time on graphs whose minimum number of edge deletions or additions to reach G is k. They first handle the k=1 edge-apex and edge-add cases, then generalize via the distance parameter, and finally apply the framework to transitive graphs.

The new piece is the uniform parameterization by arbitrary k rather than fixing it at 1, plus the clean statement that works for any base class G that already has the polynomial algorithms. The transitive-graph application is a concrete payoff since that class is known to be polynomial for these problems.

The paper is clear on the definitions and on why the distance parameter is natural. It stays focused on the two problems and does not overclaim broader impact.

The soft spot is the runtime. Enumerating which k edges or non-edges to change immediately gives only n^{O(k)} time. Reaching true 2^k dependence requires a non-enumerative method such as iterative compression or a search tree whose branching is bounded by 2 per modification. The abstract gives no indication of which technique is used or how the analysis avoids n-factors in the exponent, so the full proof in sections 3-5 is the load-bearing part. If that analysis is correct, the claim holds; if it only establishes n^{O(k)}, the headline result weakens.

This is for people working on parameterized algorithms for modification problems and hereditary classes. A reader already interested in FPT lifts for clique and independent set will find the generalization useful. It deserves a serious referee because the conditional result is a natural and cleanly stated extension, provided the runtime analysis checks out.

Referee Report

1 major / 1 minor

Summary. The paper defines the ξ_𝒢(G) distance of a graph G to a hereditary class 𝒢 as the minimum number of edge deletions or non-edge additions needed to obtain a graph in 𝒢. It claims algorithms for WMCP and WMISP on the edge-apex and edge-add classes of 𝒢, and shows that both problems admit O*(2^k) algorithms on graphs with 𝒢-edge distance k whenever they are polynomial-time solvable on 𝒢. The result is instantiated for transitive graphs, yielding O*(2^k) algorithms when the transitive-edge distance is k.

Significance. If the O*(2^k) runtime holds, the result is significant: it supplies a single-exponential FPT algorithm for weighted clique and independent set on graphs at bounded edge distance from a hereditary class, improving on the n^{O(k)} bound obtained by naive enumeration of modifications. The conditional formulation on the base class 𝒢 is appropriate, and the concrete application to transitive graphs supplies a new, usable algorithmic statement.

major comments (1)

[§§3–5] §§3–5: The headline claim is that WMCP and WMISP can be solved in O*(2^k) time (rather than n^{O(k)}) when the 𝒢-edge distance is k. Enumeration of the ≤ k modifications produces only n^{O(k)} time; therefore the analysis must establish a non-enumerative technique (iterative compression, branching search tree of factor 2, or DP over subsets of modifications) whose running-time derivation yields a true O*(2^k) bound without polynomial factors of n inside the exponent. The correctness and runtime analysis of this technique is load-bearing for the central claim.

minor comments (1)

[Abstract] Abstract: the statement that the result 'extends earlier algorithmic characterizations of the single edge-apex and edge-add classes' would be clearer if the concrete running times obtained for those single-modification cases were stated explicitly.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the manuscript. We address the major comment below.

read point-by-point responses

Referee: [§§3–5] §§3–5: The headline claim is that WMCP and WMISP can be solved in O*(2^k) time (rather than n^{O(k)}) when the 𝒢-edge distance is k. Enumeration of the ≤ k modifications produces only n^{O(k)} time; therefore the analysis must establish a non-enumerative technique (iterative compression, branching search tree of factor 2, or DP over subsets of modifications) whose running-time derivation yields a true O*(2^k) bound without polynomial factors of n inside the exponent. The correctness and runtime analysis of this technique is load-bearing for the central claim.

Authors: We agree that naive enumeration of all possible sets of at most k modifications yields only an n^{O(k)} algorithm. In §§3–5 we instead use a branching search tree with branching factor 2 on the choice of whether to include each successive modification. The search tree has depth at most k and thus at most 2^k leaves; each leaf produces a graph belonging to 𝒢 on which WMCP/WMISP is solved in polynomial time by the problem assumption on the base class. The total running time is therefore O*(2^k). We will add an explicit subsection deriving the bound from the search-tree recurrence to make the analysis fully self-contained. revision: partial

Circularity Check

0 steps flagged

No circularity; conditional O*(2^k) result requires independent technique beyond enumeration

full rationale

The paper defines G-edge distance ξ_G(G) as the min number of edge deletions/non-edge additions to reach G, then claims O*(2^k) algorithms for WMCP/WMISP on k-distant graphs conditional on poly-time solvability inside G. No equations, self-citations, or reductions in the abstract reduce this runtime to a tautology, fitted parameter, or prior self-result by construction. The extension from 1-apex/add to general k-distance and the skeptic's observation that naive enumeration yields only n^{O(k)} both indicate that any O*(2^k) bound must rest on a separate algorithmic argument (search tree, DP, or compression) whose correctness is not shown to collapse into the input assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities can be identified from the provided text.

pith-pipeline@v0.9.1-grok · 5848 in / 1041 out tokens · 30871 ms · 2026-06-29T19:34:56.439913+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

8 extracted references · 1 canonical work pages · 1 internal anchor

[1]

Borowiecki, E

M. Borowiecki, E. Drgas-Burchardt, and E. Sidorowicz.P-apex graphs. Discuss. Math. Graph Theory, 38(2):323–349, 2018

2018
[2]

Carraghan and P

R. Carraghan and P. M. Pardalos. An exact algorithm for the maximum clique problem.Oper. Res. Lett., 9(6):375–382, 1990

1990
[3]

T. Gallai. Transitiv orientierbare graphen.Acta Math. Acad. Sci. Hungar., 18:25–66, 1967

1967
[4]

M. C. Golumbic.Algorithmic Graph Theory and Perfect Graphs, volume 57 ofAnn. Discrete Math.Elsevier Sci. B.V., 2nd edition, 2004

2004
[5]

Singh and V

J. Singh and V. Sivaraman. Edge-apexing in hereditary classes of graphs. Discrete Math., 348(1):Paper No. 114234, 7, 2025

2025
[6]

Structural Bounds and Forbidden Induced Subgraphs for Edge-Add Graph Classes

J. Singh and V. Sivaraman. Hereditary classes of graphs and matroids with finitely many exclusions.arXiv, 2025. arXiv:2503.20954

work page internal anchor Pith review Pith/arXiv arXiv 2025
[7]

D. B. West.Introduction to Graph Theory. Prentice Hall, 1996

1996
[8]

Wu and J.-K

Q. Wu and J.-K. Hao. A review on algorithms for maximum clique problems. Eur. J. Oper. Res., 242(3):693–709, 2015. 11

2015

[1] [1]

Borowiecki, E

M. Borowiecki, E. Drgas-Burchardt, and E. Sidorowicz.P-apex graphs. Discuss. Math. Graph Theory, 38(2):323–349, 2018

2018

[2] [2]

Carraghan and P

R. Carraghan and P. M. Pardalos. An exact algorithm for the maximum clique problem.Oper. Res. Lett., 9(6):375–382, 1990

1990

[3] [3]

T. Gallai. Transitiv orientierbare graphen.Acta Math. Acad. Sci. Hungar., 18:25–66, 1967

1967

[4] [4]

M. C. Golumbic.Algorithmic Graph Theory and Perfect Graphs, volume 57 ofAnn. Discrete Math.Elsevier Sci. B.V., 2nd edition, 2004

2004

[5] [5]

Singh and V

J. Singh and V. Sivaraman. Edge-apexing in hereditary classes of graphs. Discrete Math., 348(1):Paper No. 114234, 7, 2025

2025

[6] [6]

Structural Bounds and Forbidden Induced Subgraphs for Edge-Add Graph Classes

J. Singh and V. Sivaraman. Hereditary classes of graphs and matroids with finitely many exclusions.arXiv, 2025. arXiv:2503.20954

work page internal anchor Pith review Pith/arXiv arXiv 2025

[7] [7]

D. B. West.Introduction to Graph Theory. Prentice Hall, 1996

1996

[8] [8]

Wu and J.-K

Q. Wu and J.-K. Hao. A review on algorithms for maximum clique problems. Eur. J. Oper. Res., 242(3):693–709, 2015. 11

2015