{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihyvxr6d2idwdtkch5e32f5ivpfr6tqvyc5owefaun6txcsl2uqta",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mmqwnmgs3g32"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.25724v1",
  "publishedAt": "2026-05-26T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Eshwar Srinivasan",
    "Ramesh Hariharasubramanian"
  ],
  "textContent": "**Authors:** Eshwar Srinivasan, Ramesh Hariharasubramanian\n\nIn 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$.",
  "title": "Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs"
}