Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
2026-05-25 • Data Structures and Algorithms
Data Structures and AlgorithmsDiscrete Mathematics
AI summaryⓘ
The authors study special graph classes created by adding or deleting a single edge from another well-understood class called hereditary classes. They focus on solving difficult problems about finding the heaviest clique or biggest independent set (WMCP and WMISP) in these new classes and extend their methods to cases where graphs are close to the base class by a few edge changes. They show that these problems can be solved efficiently when the graph differs from the hereditary class by k edges, with a running time growing like 2^k. Finally, they apply their results to graphs related to transitive graphs, proving similar computational efficiency there.
hereditary graph classesedge-apex classedge-add classWeighted Maximum Clique ProblemWeighted Maximum Independent Set Problemparameterized complexityforbidden induced subgraphstransitive graphsgraph modification distance
Authors
Eshwar Srinivasan, Ramesh Hariharasubramanian
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 $ξ_{\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$.