Identification to Subclasses of Chordal Graphs The research leading to these results has been supported by the Research Council of Norway via the BWCA Grant 314528 and the Extreme-Algorithms Grant 355137 and by the Leverhulme Trust Grant RPG-2024-182.

Petr A. Golovach, Laure Morelle, Daniël Paulusma · 2026

Read Identification to Subclasses of Chordal Graphs The research leading to these results has been supported by the Research Council of Norway via the BWCA Grant 314528 and the Extreme-Algorithms Grant 355137 and by the Leverhulme Trust Grant RPG-2024-182. by Petr A. Golovach, Laure Morelle, Daniël Paulusma (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24325.txt.

Introduction

Golovach, Morelle, and Paulusma study identification in graphs. Merging two vertices replaces them with one vertex linked to the union of their neighborhoods. They map the classical and parameterized complexity of deciding whether a graph can be identified to a chordal subclass with at most k identifications. Parameters are k and n minus k. They also map the parameterized complexity of testing whether one graph can be identified to another, using simplicial vertex counts as parameter. The result is an almost complete picture for chordal subclasses and testbed classes.

Catalog record

CREATORPetr A. Golovach, Laure Morelle, Daniël Paulusma
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121697
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.24325

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Identification to Subclasses of Chordal Graphs The research leading to these results has been supported by the Research Council of Norway via the BWCA Grant 314528 and the Extreme-Algorithms Grant 355137 and by the Leverhulme Trust Grant RPG-2024-182. Petr A. Golovach, Laure Morelle, Daniël Paulusma Abstract An identification of two vertices u u and v v in a graph replaces them with a new vertex whose neighborhood is the union of the neighborhoods of u u and v v . We study the ℋ {\cal H} -Identification problem, which is to decide whether a given graph G G can be transformed (“identified”) to a graph in ℋ {\cal H} by applying at most k 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 k and n − k n-k . We also consider the Identification problem, which is to test for two given graphs G G and H H if G G can be identified to H H . We determine the parameterized complexity of this problem when H H is a graph from one of our testbed classes, taking the number of simplicial vertices of H H as the parameter. 1 Introduction An identification of two vertices u and v in a graph G replaces u and v with a new vertex w_{uv} made adjacent to all neighbors of both u and v (equivalently, one may first add an edge between u and v if it is not already present, and then contract this edge). For a fixed class of graphs {\cal H} , we define the problem {\cal H} -Identification . The input consists of a graph G and an integer k , and the question is whether G can be transformed into some graph H\in{\cal H} using at most k identifications. We study the parameterized complexity of {\cal H} -Identification and provide a comprehensive complexity analysis for well-known subclasses {\cal H} of chordal graphs. The {\cal H} -Identification problem falls within the framework of graph modification problems, where the goal is to decide whether a given graph can be modified into a graph in a class {\cal H} using at most k operations from some specific set S of allowed modifications. For example, if S consists of vertex deletion, edge deletion, and edge contraction, then we obtain the {\cal H} - Minor problem. Another well-known variant related to \cal H -Identification is {\cal H} -Contraction , for which S consists solely of edge contraction. Most graph modification problems are NP -complete and have been extensively studied from the perspective of parameterized complexity. For example, if {\cal H} is minor-closed, such as forests, series-parallel graphs, planar graphs, and graphs of bounded treewidth, then, for fixed k , the yes-instances of both {\cal H} - Minor and \cal H -Identification form a minor-closed graph class as well. Hence, both problems can be solved in f(k,{\cal H})\cdot n^{1+o(1)} time [ 20 , 26 ] (see also [ 15 , 23 ] ). This argument does not hold for {\cal H} - Contraction [ 23 ] (see e.g. [ 14 , 16 , 17 , 18 ] ). If the graphs in {\cal H} have treewidth at most p and can be characterized in CMSO logic, such as forests, and outerplanar graphs, then the same holds for the class of yes -instances of \cal H -Identification . Hence, Courcelle’s Theorem [ 1 , 5 ] yields an g(p,k)\cdot n time algorithm. However, when {\cal H} is not minor-closed or does not have bounded treewidth, not much is known except for the case when {\cal H}=\{H\} for some single graph H . In this case, we simply write H - Identification and note that since each identification reduces the number of vertices by one, the parameter k is fixed by the instance and can be omitted. 1 1 1 The same holds for H - Contraction , but not for H - Minor [ 13 ] . While the latter is polynomial-time solvable for every fixed graph H when no bound on k is imposed [ 25 ] , both H - Contraction and H - Minor are NP -complete for some graphs H [ 3 , 13 ] and are far from being classified (see [ 13 , 21 , 22 , 27 ] ). To explain the known results, we first introduce an equivalent formulation. Two disjoint vertex subsets S and T are adjacent if there is an edge with one endpoint in S and the other in T . A graph G can be identified to a graph H if and only if V(G) can be partitioned into bags \{W(x)\mid x\in V(H)\} such that (i) for every x\in V(H) , W(x) is non-empty; and (ii) for every pair x,y\in V(H) , W(x) and W(y) are adjacent if and only if xy\in E(H) . By identifying the vertices within each W(x) to a single vertex, we obtain the graph H . We call {\cal W}=\{W(x)\mid x\in V(H)\} an H -witness structure of G . See Figure 1 for an illustration. Figure 1: An example of a graph G that can be identified to P_{4} , as shown with two different P_{4} -witness structures. Note that G is disconnected and cannot be contracted to P_{4} . For graphs G and H , a function f:V(G)\to V(H) is called a homomorphism from G to H if f(u)f(v)\in E(H) for every edge uv\in E(G) . A homomorphism f:V(G)\to V(H) is a compaction if for each edge xy\in E(H) with x\neq y , there exists an edge uv\in E(G) such that f(u)=x and f(v)=y . Here, we write x\neq y to allow for the possibility that E(H) contains self-loops xx . A graph is reflexive if all its vertices have a self-loop. For an irreflexive graph H (i.e. a graph with no self-loops), let H^{*} be the reflexive graph obtained from H by adding a self-loop to every vertex of H . Now, by using (i) and (ii), it follows that G can be identified to H if and only if there is a compaction from G to H^{*} . Thus, the H -Identification problem can be reformulated as the H^{*} -Compaction problem, which asks whether a given irreflexive graph G admits a compaction to the fixed (reflexive) graph H^{*} . Classifying the complexity of H^{*} -Compaction is still open; see also the survey [ 2 ] . However, Vikas showed that H^{*} -Compaction , and thus H -Identification , is NP -complete if H=C_{r} for any r\geq 4 [ 28 ] , but in XP when parameterized by |V(H)| if H is chordal [ 29 ] ; a graph is chordal if it has no induced cycle on four or more vertices. This result for H - Identification is tight in the sense that even K_{1,\ell} - Identification is W[1] -hard when parameterized by \ell , where K_{1,\ell} denotes the star on \ell+1 vertices (which is chordal). Indeed, by (i) and (ii), a graph G without isolated vertices can be identified to K_{1,\ell} if and only if G has an independent

Read the complete text