{"id":"arxiv/2604.24325","url":"https://arxiv.org/abs/2604.24325","tags":["cs.DS","cs.CC","math.CO"],"score":0,"title":"Identification to Subclasses of Chordal Graphs","domain":"cs.DS","source":"arxiv","authors":["Petr A. Golovach","Laure Morelle","Daniël Paulusma"],"reviews":0,"subject":"cs.DS","summary":"An identification of two vertices $u$ and $v$ in a graph replaces them with a new vertex whose neighborhood is the union of the neighborhoods of $u$ and $v$. We study the {\\sc ${\\cal H}$-Identification} problem, which is to decide whether a given graph $G$ can be transformed (``identified'') to a graph in ${\\cal H}$ by applying at most $k$ vertex identifications. We determine the classical and parameterized complexity of this problem for various subclasses ${\\cal H}$ of chordal graphs, obtaining an almost complete picture for two parameters: $k$ and $n-k$. We also consider the {\\sc…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-27","reactions":{}}