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$.
| Comments: | 10 pages |
| Subjects: | Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO) |
| Cite as: | arXiv:2605.25724 [cs.DS] |
| (or arXiv:2605.25724v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25724 arXiv-issued DOI via DataCite (pending registration) |
From: Ramesh Hariharasubramanian [view email]
[v1]
Mon, 25 May 2026 11:30:48 UTC (9 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。