Identification to Subclasses of Chordal Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910169385926656 |
|---|---|
| author | Golovach, Petr A. Morelle, Laure Paulusma, Daniël |
| author_facet | Golovach, Petr A. Morelle, Laure Paulusma, Daniël |
| contents | 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 Identification} problem, which is to test for two given graphs $G$ and $H$ if $G$ can be identified to $H$. We determine the parameterized complexity of this problem when $H$ is a graph from one of our testbed classes, taking the number of simplicial vertices of $H$ as the parameter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_24325 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Identification to Subclasses of Chordal Graphs Golovach, Petr A. Morelle, Laure Paulusma, Daniël Data Structures and Algorithms Computational Complexity Combinatorics 05C85, 68R10, 05C75 F.2.2; G.2.2 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 Identification} problem, which is to test for two given graphs $G$ and $H$ if $G$ can be identified to $H$. We determine the parameterized complexity of this problem when $H$ is a graph from one of our testbed classes, taking the number of simplicial vertices of $H$ as the parameter. |
| title | Identification to Subclasses of Chordal Graphs |
| topic | Data Structures and Algorithms Computational Complexity Combinatorics 05C85, 68R10, 05C75 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2604.24325 |