{"id":"arxiv/2605.25724","url":"https://arxiv.org/abs/2605.25724","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs","domain":"cs.DS","source":"arxiv","authors":["Eshwar Srinivasan","Ramesh Hariharasubramanian"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-25","reactions":{}}