A Finer View of the Parameterized Landscape of Labeled Graph Contractions

Mathur, Yashaswini; Tale, Prafullkumar

doi:10.4230/LIPIcs.FSTTCS.2025.43

A Finer View of the Parameterized Landscape of Labeled Graph Contractions

Yashaswini Mathur

Indian Institute of Science Education and Research Bhopal, India Prafullkumar Tale

Indian Institute of Science Education and Research Pune, India

Abstract

We study the Labeled Contractibility problem, where the input consists of two vertex-labeled graphs $G$ and $H$ , and the goal is to determine whether $H$ can be obtained from $G$ via a sequence of edge contractions.

Lafond and Marchand [WADS 2025] initiated the parameterized complexity study of this problem, showing it to be ${\mathsf{W}}[1]$ -hard when parameterized by the number $k$ of allowed contractions. They also proved that the problem is fixed-parameter tractable when parameterized by the tree-width tw of $G$ , via an application of Courcelle’s theorem resulting in a non-constructive algorithm.

In this work, we present a constructive fixed-parameter algorithm for Labeled Contractibility with running time $2^{\mathcal{O}(\textsf{tw}^{2})}\cdot|V(G)|^{\mathcal{O}(1)}$ . We also prove that unless the Exponential Time Hypothesis (ETH) fails, it does not admit an algorithm running in time $2^{o(\textsf{tw}^{2})}\cdot|V(G)|^{\mathcal{O}(1)}$ . This result adds Labeled Contractibility to a small list of problems that admit such a lower bound and matching algorithm.

We further strengthen existing hardness results by showing that the problem remains $\mathsf{NP}$ -complete even when both input graphs have bounded maximum degree. We also investigate parameterizations by $(k+\delta(G))$ where $\delta(G)$ denotes the degeneracy of $G$ , and rule out the existence of subexponential-time algorithms. This answers question raised in Lafond and Marchand [WADS 2025]. We additionally provide an improved $\mathsf{FPT}$ algorithm with better dependence on $(k+\delta(G))$ than previously known. Finally, we analyze a brute-force algorithm for Labeled Contractibility with running time $|V(H)|^{\mathcal{O}(|V(G)|)}$ , and show that this running time is optimal under ETH.

Keywords and phrases:

Labeled Contraction, ETH Lower-bound, Treewidth, NP-hard

Funding:

Prafullkumar Tale: INSPIRE Faculty Fellowship by DST, Govt of India.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Fixed parameter tractability

Editors:

C. Aiswarya, Ruta Mehta, and Subhajit Roy

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Graph modification problems are a foundational topic in algorithmic graph theory. A general formulation of the $\mathcal{F}$ -M-Modification problem asks: given a graph $G$ and a fixed set M of allowed modification operations (such as vertex deletion, edge addition/deletion, or edge contraction), can $G$ be transformed into a graph in class $\mathcal{F}$ using at most $k$ operations from M.

It is well known that the $\mathcal{F}$ -M-Modification problem is $\mathsf{NP}$ -hard for many natural graph classes $\mathcal{F}$ when M consists of vertex or edge deletions [54, 42]. Hardness results for edge contraction were first shown by Watanabe et al. [53] and Asano and Hirata [4]. It is noteworthy that while the problem becomes trivially solvable when M includes only vertex or edge deletions and $\mathcal{F}$ is a singleton, this is not the case for edge contractions. In fact, Brouwer and Veldman [9] established that the problem remains $\mathsf{NP}$ -complete even when $\mathcal{F}$ is a singleton containing a small graph, such as a cycle or a four-vertex path. This difference highlights the increased algorithmic complexity introduced by edge contractions compared to vertex or edge deletions.

Graph modification problems have played a central role in the development of parameterized complexity and the design of key algorithmic techniques. A representative list of relevant works includes [7, 8, 11, 12, 13, 14, 17, 23, 24, 25, 27, 29]. For a comprehensive overview, the survey by Crespelle et al. [18] provides an in-depth discussion of modification problems involving edge deletion, editing, and completion.

A series of recent papers have studied the parameterized complexity of $\mathcal{F}$ -Contraction for various graph classes $\mathcal{F}$ , including paths and trees [35], generalizations and restrictions of trees [1, 2], cactus graphs [40], bipartite graphs [34, 36], planar graphs [33], grids [50], cliques [10], split graphs [3], chordal graphs [44], bicliques [47], and degree-constrained graph classes [5, 32, 51].

Recently, Lafond and Marchand [41] initiated the parameterized study of edge contraction problems in uniquely labeled graphs, where each vertex has a different label. They introduced the following problem:

Labelled Contractibility

Input: Two vertex-labeled graphs $G$ and $H$ with $V(H)\subseteq V(G)$ .

Question: Is $H$ a labeled contraction of $G$ ?

See Definition 6 in Section 2 for formal definitions.

They also introduced a generalization, motivated by applications in phylogenetic networks [46], which are rooted acyclic directed graphs with labeled leaves representing evolutionary histories:

Maximum Common Labeled Contraction

Input: Two vertex-labeled graphs $G$ and $H$ , and an integer $k$ .

Question: Do there exist labeled contraction sequences $S_{1}$ and $S_{2}$ such that $G/S_{1}=H/S_{2}$ and $|S_{1}|+|S_{2}|\leq k$ ?

This second problem is closely related to the first. As shown in [41], $H$ is a labeled contraction of $G$ if and only if there exists a common contraction of both $G$ and $H$ to a labeled graph $H^{\prime}$ of size at least $|V(H)|$ . This equivalence allows complexity results to be transferred between the two problems. The same work provides additional applications and results.

Lafond and Marchand [41] showed that Labeled Contractibility is ${\mathsf{W}}[1]$ -hard when parameterized by the natural parameter $k=|V(G)\setminus V(H)|$ , the number of allowed edge contractions. This motivates the exploration of structural parameters. They established that the problem admits a fixed-parameter tractable ( $\mathsf{FPT}$ ) algorithm when parameterized by the treewidth tw of the input graph $G$ by invoking a variation of Courcelle’s theorem [26, Theorem 11.73]. However, this approach yields a non-elementary dependence on the parameter.

Our first contribution is a constructive dynamic programming algorithm with a running time that is singly exponential in $\textsf{tw}^{2}$ . We complement this with a matching lower bound under the Exponential Time Hypothesis (ETH):

Theorem 1.

Labeled Contractibility

$\blacksquare$

admits an algorithm running in time $2^{\mathcal{O}(\textsf{tw}^{2})}\cdot|V(G)|^{\mathcal{O}(1)}$ ; but
$\blacksquare$

does not admit an algorithm running in time $2^{o(\textsf{tw}^{2})}\cdot|V(G)|^{\mathcal{O}(1)}$ , unless the ETH fails.

We note that this lower bound also holds when parameterized by the pathwidth, which is a larger parameter. Most known $\mathsf{FPT}$ -algorithms that use dynamic programming on tree decompositions have running times, and matching lower bounds, of the form $2^{\mathcal{O}(\textsf{tw})}\cdot n^{\mathcal{O}(1)}$ [19, Chapters 7,13] or $2^{\mathcal{O}(\textsf{tw}\log\textsf{tw})}\cdot n^{\mathcal{O}(1)}$ [43, 21]. For a relatively rare set of problems exhibits a double-exponential dependence on treewidth, see [30, 52, 16] and references within. To our knowledge, the only problems with single-exponential-but-polynomial dependencies on pathwidth are mentioned in [20, 48, 49]. Similar results parameterized by vertex cover number can be found in [3, 31, 6, 15].

Lafond and Marchand [41] observed that smaller parameters such as degeneracy do not yield tractable results. Specifically, it is known that the Maximum Common Labeled Contraction problem is $\mathsf{NP}$ -hard even when both input graphs have constant maximum degree (and thus constant degeneracy), and that Labeled Contractibility is $\mathsf{NP}$ -hard for graphs of bounded degeneracy [45, Theorem 8]. We strengthen this latter result by proving hardness under an even stricter constraint:

Theorem 2.

Labeled Contractibility is $\mathsf{NP}$ -hard even when both $G$ and $H$ have bounded maximum degree.

These results suggest that tractability is unlikely when parameterizing solely by the solution size $k$ or the degeneracy $\delta(G)$ . Nevertheless, Lafond and Marchand [41] showed the problem becomes tractable for the combined parameter $(k+\delta(G))$ , yielding an algorithm with a running time of $(\delta(G)+2k)^{k}\cdot n^{\mathcal{O}(1)}$ . They asked whether a subexponential-time algorithm exists for this parameterization, a question we resolve negatively:

Theorem 3.

Labeled Contractibility does not admit an algorithm running in time $2^{o(|V(G)|+|E(G)|)}$ even when both $G$ and $H$ have bounded degeneracy, unless the ETH fails.

This theorem rules out the possibility of a subexponential-time algorithm parameterized by $(k+\delta(G))$ under the assumption of the ETH. We also provide the following algorithm, which improves upon previous work:

Theorem 4.

Labeled Contractibility can be solved in time $(\delta(H)+1)^{k}\cdot|V(G)|^{\mathcal{O}(1)}$ , where $k$ is the solution size and $\delta(H)$ is the degeneracy of $H$ .

This algorithm improves upon the $(\delta(H)+k)^{k}\cdot n^{\mathcal{O}(1)}$ algorithm from [41, Section 3.3]. The previous result relied on the bound $\delta(H)\leq\delta(G)+k$ . We refine this with a tighter upper bound: $\delta(H)\leq\delta(G)\cdot\frac{|V(G)|}{|V(G)|-k}$ . For cases where $|V(G)|\geq(1+\epsilon)\cdot k$ , this bound yields $\delta(H)\leq\delta(G)\cdot c_{\epsilon}$ , where $\epsilon$ and $c_{\epsilon}$ are absolute constants. This substantially improves the previous analysis, leading to a more efficient algorithm under these conditions.

Finally, as our last contribution, we analyze a brute-force algorithm for Labeled Contractibility and establish its optimality under the ETH. Notably, our analysis also applies to the more general Maximum Common Labeled Contraction problem.

Theorem 5.

Labeled Contractibility

$\blacksquare$

admits an algorithm running in time $|V(H)|^{\mathcal{O}(|V(G)|)}$ ; but
$\blacksquare$

does not admit an algorithm running in time $|V(H)|^{o(|V(G)|)}$ , unless the ETH fails.

Organization.

We adopt standard notation from graph theory and parameterized complexity, as outlined in Section 2. In Section 3, we present a dynamic programming algorithm based on tree decompositions and establish a matching lower bound. Specifically, we provide a parameter-preserving reduction from the Sub-Cubic Partitioned Vertex Cover problem [3], which proves Theorem 1. Section 4 proves Theorem 2 by a reduction from Positive-Not-All-Equal-SAT, showing $\mathsf{NP}$ -hardness even for graphs of bounded maximum degree. Section 5 is dedicated to a conditional lower bound under the ETH. Using a reduction from 1-in-3-SAT, we prove this result even when both input graphs have bounded degeneracy. We also present an improved $\mathsf{FPT}$ algorithm for the combined parameter $(k+\delta(G))$ . These results together establish Theorems 3 and 4. Section 6 analyzes a brute-force algorithm and establishes its optimality under the ETH. This is achieved via a reduction from the Cross Matching problem [28] and establishes Theorem 5.

For more comprehensive details, including the full proofs and additional technical arguments, we refer the reader to the longer version of this paper.

2 Preliminaries

Throughout this work, we consider uniquely labeled graphs. Following the convention in [41], we refer to vertices directly by their labels rather than using explicit labeling functions. Two labeled graphs $G$ and $H$ are considered equal, denoted $G=H$ , if and only if $V(G)=V(H)$ and $E(G)=E(H)$ . This is distinct from the standard notion of graph isomorphism, where a bijection $\sigma:V(G^{\prime})\to V(H^{\prime})$ exists such that $(u,v)\in E(G^{\prime})$ if and only if $(\sigma(u),\sigma(v))\in E(H^{\prime})$ . In our setting, we assume that the labels of $H$ are a subset of those of $G$ .

Definition 6.

Let $G$ be a labeled graph and $(u,v)\in E(G)$ . The labeled contraction of the edge $(u,v)$ is an operation that transforms $G$ by:

$\blacksquare$

For every vertex $w\in N(v)\setminus N[u]$ , adding the edge $(u,w)$ to $G$ .
$\blacksquare$

Removing the vertex $v$ and all incident edges.

The resulting graph is denoted by $G/(u,v)$ .

Note that in general, $G/(u,v)\neq G/(v,u)$ , as the vertex that is retained after the contraction (and thus the label) is different. The two resulting graphs are, however, isomorphic under the standard unlabeled notion. For simplicity, in the remainder of this paper, we assume all contractions are labeled and refer to them simply as contractions.

A labeled contraction sequence $S$ on a graph $G$ is a sequence of vertex pairs $S=((u_{1},v_{1}),\ldots,(u_{k},v_{k}))$ such that for each $i\in\{0,\ldots,k-1\}$ , if $G^{i}$ is the graph obtained after the first $i$ contractions (with $G^{0}:=G$ ), then $(u_{i+1},v_{i+1})\in E(G^{i})$ and $G^{i+1}=G^{i}/(u_{i+1},v_{i+1})$ . The graph obtained after the full sequence is denoted by $G/S$ . If $S$ is not a valid contraction sequence on $G$ , then $G/S$ is undefined. We say that a graph $H$ is a labeled contraction of $G$ if there exists a contraction sequence $S$ such that $G/S=H$ . A graph $M$ is a common labeled contraction of graphs $G$ and $H$ if it is a labeled contraction of both. A maximum common labeled contraction of $G$ and $H$ is a common labeled contraction with the largest possible number of vertices.

Consider two graphs $H$ and $G$ such that $V(H)\subseteq V(G)$ .

Definition 7.

A witness structure of $G$ into $H$ is a partition $\mathcal{W}=\{W_{1},\ldots,W_{|V(H)|}\}$ of $V(G)$ into non-empty sets satisfying:

$\blacksquare$

For each $W_{i}\in\mathcal{W}$ , the induced subgraph $G[W_{i}]$ is connected.
$\blacksquare$

Each $W_{i}$ contains exactly one vertex from $V(H)$ , called its representative vertex.
$\blacksquare$

For any distinct $u,v\in V(H)$ , the edge $(u,v)\in E(H)$ if and only if the sets in $\mathcal{W}$ containing $u$ and $v$ are adjacent in $G$ .

There is a natural bijection between the sets in $\mathcal{W}$ and the vertices of $H$ via their representatives. It is known that $H$ is a labeled contraction of $G$ if and only if a witness structure of $G$ into $H$ exists (see Observation 2 in [41]). Furthermore, contractions within a single witness set can be performed in any order as long as the representative vertex is preserved (Observation 3 in the same work). For any vertex $u\in V(G)$ , we denote by $\mathcal{W}(u)\in\mathcal{W}$ the unique set that contains $u$ .

3 Parameterized by Treewidth

In this section, we present the proof of Theorem 1 which we restate.

Theorem 1. [Restated, see original statement.]

Labeled Contractibility

$\blacksquare$

admits an algorithm running in time $2^{\mathcal{O}(\textsf{tw}^{2})}\cdot|V(G)|^{\mathcal{O}(1)}$ ; but
$\blacksquare$

does not admit an algorithm running in time $2^{o(\textsf{tw}^{2})}\cdot|V(G)|^{\mathcal{O}(1)}$ , unless the ETH fails.

In the first subsection, we describe the algorithmic result by presenting a dynamic programming algorithm on tree decomposition. In the second subsection, we establish a matching conditional lower bound.

3.1 Algorithmic Result

In this subsection we will present a dynamic programming (DP) based algorithm for the Labeled Contraction problem when parameterized by treewidth of the input graph. For the sake of completeness, we start with the standard definitions.

Definition 8 ([19]).

A tree decomposition of a graph $G$ is a pair $(\mathcal{T},\{X_{t}\}_{t\in V(\mathcal{T})})$ , where $\mathcal{T}$ is a rooted tree and each node $t\in V(\mathcal{T})$ is associated with a set $X_{t}\subseteq V(G)$ , referred to as a bag, satisfying the following conditions:

$\blacksquare$

For every vertex $v\in V(G)$ , the set $\{t\in V(\mathcal{T})\mid v\in X_{t}\}$ is nonempty and induces a connected subtree of $\mathcal{T}$ ;
$\blacksquare$

For every edge $\{u,v\}\in E(G)$ , there exists a node $t\in V(\mathcal{T})$ such that $\{u,v\}\subseteq X_{t}$ .

The width of a tree decomposition is $\max_{t\in V(\mathcal{T})}|X_{t}|-1$ . The treewidth of $G$ , denoted $\textsf{tw}(G)$ , is the minimum width over all valid tree decompositions of $G$ .

Definition 9 ([19]).

A nice tree-decomposition of a graph $G$ is a rooted tree-decomposition $(\mathcal{T},\{X_{t}\}_{t\in V(\mathcal{T})})$ where $\mathcal{T}$ is rooted at $r$ with $X_{r}=\emptyset$ , and each node of $\mathcal{T}$ belongs to one of the following types:

$\blacksquare$

A leaf node $t$ is a leaf of $\mathcal{T}$ with $X_{t}=\emptyset$ .
$\blacksquare$

An introduce vertex node $t$ has one child $t_{1}$ such that $X_{t}=X_{t_{1}}\cup\{x\}$ , for some $x\notin X_{t_{1}}$ .
$\blacksquare$

A forget node $t$ has one child $t_{1}$ such that $X_{t}=X_{t_{1}}\setminus\{x\}$ , where $x\in X_{t_{1}}$ .
$\blacksquare$

An introduce edge node $t$ has one child $t^{\prime}$ with $X_{t}=X_{t^{\prime}}$ , and is labeled with an edge $\{u,v\}\in E(G)$ such that $\{u,v\}\subseteq X_{t}$ . We say that the edge $\{u,v\}$ is introduced at $t$ ;
$\blacksquare$

A join node $t$ has two children $t_{1}$ and $t_{2}$ such that $X_{t}=X_{t_{1}}=X_{t_{2}}$ .

Without loss of generality, we assume that a nice tree-decomposition of width tw is provided. If not, one can construct an optimum tree decomposition in time $2^{\mathcal{O}(\text{tw}^{2})}n^{\mathcal{O}(1)}\nobreak\$ [39].

Recall that we denote $G\cup H$ as the graph with vertex set $V(G)$ and edge set $E(G)\cup E(H)$ . The following lemma enables us to work with tree decompositions of $G\cup H$ instead of just $G$ , which is crucial for our formulation.

Lemma 10 ([41], Lemma 13).

If $H$ is a contraction of $G$ , then $\textsf{tw}(G\cup H)\leq 2\textsf{tw}(G)$ .

Henceforth, we fix a nice tree decomposition $\mathcal{T}$ of $G\cup H$ . This choice is crucial because it ensures that for any edge $(u,v)\in E(H)$ , there exists some bag $X_{t}$ such that $u,v\in X_{t}$ , a condition that is not guaranteed in a tree decomposition of $G$ alone. For each node $t\in\mathcal{T}$ , we define $G_{t}$ and $H_{t}$ to be the subgraphs of $G$ and $H$ , respectively, induced by the union of all bags in the sub-tree of $\mathcal{T}$ rooted at $t$ .

We now introduce the key definitions for the DP-state at a node $t$ of the tree-decomposition to convey the main ideas of the algorithm. The formal proof follows.

3.1.1 Witness Structures and Functional Representation

Assume that $H$ is a contraction of $G$ , and let $\mathcal{W}=\{W_{1},\dots,W_{|V(H)|}\}$ denote a witness structure for this contraction. We represent $\mathcal{W}$ functionally using a pair of auxiliary functions: a parent function and an originator function.

Definition 11 (Parent function).

Given a witness structure $\mathcal{W}$ , a function $\sigma^{\prime}:V(G)\to V(G)$ is a parent function with respect to $\mathcal{W}$ if there exists a collection of rooted trees $\{T_{i}\}_{i=1}^{k}$ , where each $T_{i}$ is a spanning tree of $G[W_{i}]$ rooted at the unique vertex of $W_{i}\cap V(H)$ , such that:

1.

For all $u\in W_{i}\setminus V(H)$ , $\sigma^{\prime}(u)$ is the parent of $u$ in $T_{i}$ ; and
2.

For the unique vertex $u\in W_{i}\cap V(H)$ , $\sigma^{\prime}(u)=u$ .

Definition 12 (Originator function).

Given a witness structure $\mathcal{W}$ , a function $\tau^{\prime}:V(G)\to V(H)$ is an originator function with respect to $\mathcal{W}$ if for every $u\in W_{i}$ , $\tau^{\prime}(u)$ is the unique vertex in $W_{i}\cap V(H)$ .

Note that any valid originator function $\tau^{\prime}$ defines a partition of $V(G)$ into the witness sets $\mathcal{W}$ . Also, for any vertex $u\in V(G)$ , there exists a bag that contains both $u$ and $\sigma^{\prime}(u)$ , but not necessarily $\tau^{\prime}(u)$ .

A pair $(\sigma^{\prime},\tau^{\prime})$ is said to be consistent if for every $u\in V(G)$ $\tau^{\prime}(u)=\tau^{\prime}(\sigma^{\prime}(u))$ , i.e. $u$ and its parent $\sigma^{\prime}(u)$ belong to the same witness set. In the remainder of the discussion, we assume all parent-originator pairs to be consistent unless stated otherwise. Although $\tau^{\prime}$ can be derived from $\sigma^{\prime}$ by following parent pointers up to a vertex in $V(H)$ , we maintain both functions explicitly for algorithmic clarity.

Definition 13 (Witness impression).

Every witness structure $\mathcal{W}$ corresponds to pair $(\sigma^{\prime},\tau^{\prime})$ , called its witness-impression, where $\sigma^{\prime}$ is a parent function and $\tau^{\prime}$ is the corresponding originator function.

Definition 14 (Seed impression).

Let $(\sigma^{\prime},\tau^{\prime})$ be an impression of a witness structure. A pair of partial functions $(\sigma,\tau)$ , with $\sigma:V(G_{t})\to V(G_{t})\cup\{\star\}$ and $\tau:V(G_{t})\to V(H_{t})\cup\{\star\}$ , is a seed impression of $(\sigma^{\prime},\tau^{\prime})$ at $t$ if:

$\blacksquare$

For every vertex $u\in V(G_{t})\setminus X_{t}$ , $\sigma(u)=\sigma^{\prime}(u)$ and $\tau(u)=\tau^{\prime}(u)$ .
$\blacksquare$

For a vertex $u\in X_{t}$ , if $\sigma^{\prime}(u)\in V(G_{t})$ then $\sigma(u)=\sigma^{\prime}(u)$ otherwise $\sigma(u)=\star$ . The function $\tau$ is derived from $\sigma$ by following parent pointers up to either a vertex in $V(H)$ or $\star$ .

Note that $(\sigma,\tau)$ is not merely the restriction of $(\sigma^{\prime},\tau^{\prime})$ to $V(G_{t})$ , since a vertex $u$ such that $\sigma^{\prime}(u)\notin V(G_{t})$ might satisfy $\tau^{\prime}(u)\in V(G_{t})$ , but we still assign $\tau(u)=\star$ . Note that in Figure 1, $\tau^{\prime}(u_{1})\in G_{t}$ but since $\sigma^{\prime}(u_{1})\notin G_{t}$ we assign $\tau(u_{1})=\star$ .

We now classify each vertex in the bag $X_{t}$ into one of three types, according to the seed impression $(\sigma,\tau)$ :

Definition 15 (Types of vertices).

Let $t\in V(\mathcal{T})$ be a node with bag $X_{t}$ , and let $(\sigma,\tau)$ be a seed impression at $t$ . Then each vertex $u\in X_{t}$ is assigned one of the following types:

$\blacksquare$

Requester: $\sigma(u)\in V(G_{t})$ and $\tau(u)\in V(H_{t})$ (i.e., both are defined); $u$ is ready to request adjacency requirements in $H$ .
$\blacksquare$

Dependent: $\sigma(u)\in V(G_{t})$ but $\tau(u)=\star$ ; $u$ has been contracted into its parent and depends on the parent node’s decision regarding the partition.
$\blacksquare$

Explorer: $\sigma(u)=\star$ (implying $\tau(u)=\star$ ); $u$ is still exploring who its parent will be.

We classify the pair of requester vertices into the following three parts.

Definition 16 (Requester pair classification).

Let $u,v\in X_{t}$ be requester vertices with $\tau(u)=h_{u}$ , $\tau(v)=h_{v}$ . We say the pair $(u,v)$ is

$\blacksquare$

invalid (inv) if $(h_{u},h_{v})\notin E(H)$ but $\tau^{-1}(h_{u}),\tau^{-1}(h_{v})$ are adjacent in $G_{t}$ ,
$\blacksquare$

unsatisfied (unsat) if $(h_{u},h_{v})\in E(H)$ and $\tau^{-1}(h_{u}),\tau^{-1}(h_{v})$ are not adjacent in $G_{t}$ , and
$\blacksquare$

satisfied (sat), otherwise.

For a vertex $u\in V(G)$ , we define the set $\textsf{des}(u)\subseteq V(G)$ of descendants of $u$ with respect to a function $\sigma^{\prime}:V(G)\to V(G)$ as follows:

\textsf{des}(u)=\left\{v\in V(G)\;\middle|\;\text{there exists an integer }% \ell\geq 0\text{ such that }\sigma^{\prime(\ell)}(v)=u\right\},

where $\sigma^{\prime(0)}(v)=v$ , and for $\ell\geq 1$ , $\sigma^{\prime(\ell)}(v)=\sigma^{\prime}(\sigma^{\prime(\ell-1)}(v))$ . That is, $\textsf{des}(u)$ consists of all vertices $v$ for which repeated applications of $\sigma^{\prime}$ eventually reach $u$ , including $u$ itself.

Definition 17 (Pseudo-adjacency).

Let $u, v$ be two vertices in $X_{t}$ . Then, we say $u$ and $v$ are pseudo-adjacent if sets $\textsf{des}(u)$ and $\textsf{des}(v)$ are adjacent in $G_{t}$ .

3.1.2 Signatures and Dynamic Programming States

Suppose the graph $G$ admits an $H$ -witness structure $\mathcal{W}$ , and let $(\sigma^{\prime},\tau^{\prime})$ be the corresponding witness-impression as specified in Definition 13. Let $T$ be a tree decomposition of the graph $G\cup H$ , and let $t$ be a node of $T$ .

Definition 18 (Partial Solution).

We define a partial solution at node $t$ as a tuple $P=(\sigma,\tau,\mathcal{R},\mathcal{A}),$ with the following components:

$\blacksquare$

$(\sigma,\tau)$ is a seed impression of the witness-impression $(\sigma^{\prime},\tau^{\prime})$ , restricted to the bag $X_{t}$ at $t$ , as specified in Definition 14,
$\blacksquare$

$\mathcal{R}\subseteq R\times R\times\{\textsf{inv},\textsf{sat},\textsf{unsat}\}$ is a set of labeled pairs, where $R\subseteq X_{t}$ denotes the set of requester vertices contained in $X_{t}$ as per Definition 15. Each element $(u,v,\ell)\in\mathcal{R}$ represents a label $\ell\in\{\textsf{inv},\textsf{sat},\textsf{unsat}\}$ assigned to the pair $(u,v)$ , as per Definition 16,
$\blacksquare$

$\mathcal{A}\subseteq X_{t}\times X_{t}$ records unordered pairs of vertices in $X_{t}$ that are pseudo-adjacent to each other, as per Definition 17.

We now refer to Figure 1 to provide intuition for the above definitions. The figure shows the graph $H$ together with a part of the tree decomposition of $G\cup H$ (we do not explicitly draw $G$ ). The rounded outlines indicate the witness structure for the contraction, whenever it exists: each group contains exactly one node of $H$ , representing the collection of vertices that contract to it. Note that $\sigma(u_{2})=u_{1}$ , $\tau(u_{2})=\star$ , and $\tau(u_{1})=\sigma(u_{1})=\star$ . Since the edge $(u_{3},u_{4})$ is an edge we processed earlier in the DP, we may store $(u_{7},u_{5},\textsf{sat})\in\mathcal{R}$ for $X_{t}$ . On the other hand, because the edge $(u_{6},u_{5})$ has not yet been introduced, the edge $(h_{2},h_{3})$ does not appear in the current structure, so we have $(u_{2},u_{5},\textsf{unsat})$ . Furthermore, observe that $(u_{8},u_{5})$ and $(u_{7},u_{5})$ belong to $\mathcal{A}$ , whereas $(u_{9},u_{5})\notin\mathcal{A}$ . In this way, all relevant sets are defined for the dynamic programming.

(a) Illustration of

G_{t}

and

X_{t}

.

(b) Graph

H

.

Figure 1: Depicting definitions relevant to the algorithm.

We now provide a formal definition for the same.

Note that, as it is standard in the case of dynamic programming on tree decomposition, we will not compute all the partial solution at node $t$ but rather just store unique signatures of all the partial solutions at $t$ . The signature $S$ of a partial solution $P=(\sigma,\tau,\mathcal{R},\mathcal{A})$ is $(\sigma|_{X_{t}},\tau|_{X_{t}},\mathcal{R},\mathcal{A})$ .

States of the Dynamic Programming Algorithms

Definition 19 (Signature).

A state of dynamic programming table will be a tuple $S=(\sigma,\tau,\mathcal{R},\mathcal{A})$ such that

$\blacksquare$

$\sigma:X_{t}\to X_{t}\cup\{\star\}$ (which will emulate a parent function),
$\blacksquare$

$\tau:X_{t}\to V(H_{t})\cup\{\star\}$ (which will emulate an originator function),
$\blacksquare$

$\mathcal{R}\subseteq R\times R\times\{\textsf{inv},\textsf{sat},\textsf{unsat}\}$ is a set of labeled pairs representing a label $\ell\in\{\textsf{inv},\textsf{sat},\textsf{unsat}\}$ assigned to the pair $(u,v)$ , as per Definition 16, and
$\blacksquare$

$\mathcal{A}$ is the collection of pair of vertices in $X_{t}$ that are pseudo-adjacent with each other.

The condition on functions ensures that at present $\sigma$ and $\tau$ are valid candidate to be a parent function and an originator function.

For a node $t$ in tree decomposition $T$ , we construct a dynamic-programming algorithm that sets the value $\textbf{d}[S,t]$ to True if and only if $S$ is a signature of some partial solution $P$ at node $t$ . Otherwise, we set it to False. Initially, all entries are set to False. For any signature $S=(\sigma,\tau,\mathcal{R},\mathcal{A})$ , if $\mathcal{R}$ contains an entry of the type $(u,v,\textsf{inv})$ then $\textbf{d}[S,t]$ is set to False and it will never be changed.

We remark that the technical challenge in designing the dynamic programming algorithm was to find an appropriate, concise expression for the partial solution, which was discussed above. At any node $t$ of the tree decomposition, the number of distinct signatures that can be stored is bounded by $2^{\mathcal{O}(\textsf{tw}^{2})}$ , where tw denotes the width of the decomposition. This bound arises from the fact that the signature must encode information pertaining to all pairs of vertices in the bag $X_{t}$ . The specific process to update the dynamic programming table is a standard exhaustive enumeration over compatible signatures at the child node(s) and applying the corresponding update rule. For full details on the update rules and their proof of correctness, we refer the reader to the longer version of this paper. The time required to process each node is polynomial in the number of signatures. Consequently, the overall running time of the algorithm is bounded by $2^{\mathcal{O}(\textsf{tw}^{2})}\cdot|V(G)|^{\mathcal{O}(1)}$ . This concludes the proof of the algorithmic result mentioned in Theorem 1.

3.2 Conditional Lower Bound

In this section, we demonstrate that unless (ETH) fails, Labeled Contraction does not admit an algorithm running in time $2^{o(\textsf{tw}^{2})}\cdot|V(G)|^{\mathcal{O}(1)}$ , where tw is the treewidth of the input graph $G$ . To obtain the lower bound, we reduce from a special case of Vertex Cover on sub-cubic graphs, defined in [3] as follows:

Sub-Cubic Partitioned Vertex Cover (Sub-Cubic PVC)

Input: A sub-cubic graph $G$ ; an integer $t$ ; for $i\in[t]$ , an integer $k_{i}\geq 0$ ; a partition $\mathcal{P}=\{C_{1},\ldots,C_{t}\}$ of $V(G)$ such that $t\in\mathcal{O}(\sqrt{|V(G)|})$ and for all $i\in[t]$ , $C_{i}$ is an independent set and $|C_{i}|\in\mathcal{O}(\sqrt{|V(G)|})$ . Furthermore, for $i,j\in[t]$ , $i\neq j$ , $|E(G[C_{i}\cup C_{j}])\cap E(G)|=1$ .

Question: Does $G$ have a vertex cover $X$ such that for all $i\in[t]$ , $|X\cap C_{i}|\leq k_{i}$ ?

Proposition 20 (Theorem 3.9 in [3]).

Sub-Cubic PVC does not admit an algorithm running in time $2^{o(n)}$ , unless the ETH fails.

We now prove the lower bound in Theorem 1.

Let $(G,\mathcal{P}=\{C_{1},C_{2},\ldots,C_{t}\},k_{1},\ldots,k_{t})$ be an instance of the Sub-Cubic PVC problem, where $n=|V(G)|$ . We construct an instance $(G^{\prime},H^{\prime})$ of the Labeled Contraction problem as follows.

Construction of $G^{\prime}$ .

We begin by setting $V(G^{\prime})\supseteq V(G)$ , i.e., all vertices of $G$ are copied into $G^{\prime}$ (without copying any edges). For each partition $C_{i}\in\mathcal{P}$ , we introduce a set $S_{i}$ consisting of $\binom{|C_{i}|}{k_{i}+1}$ new vertices in $G^{\prime}$ , where each vertex $s\in S_{i}$ corresponds uniquely to a subset $C_{i}^{\prime}\subseteq C_{i}$ of size exactly $k_{i}+1$ . For each such vertex $s\in S_{i}$ , we add edges between $s$ and every vertex in the subset $C_{i}$ . Additionally, for every $C_{i}\in\mathcal{P}$ , we introduce three auxiliary vertices $\{x_{i},y_{i},z_{i}\}$ in $G^{\prime}$ . Each of these vertices is connected to every vertex in $C_{i}$ . Moreover, we add edges $(z_{i},x_{i})$ and $(z_{i},y_{i})$ . Each vertex $s\in S_{i}$ is connected to the corresponding vertex $x_{i}$ .

We now encode the edges in $G$ . Consider a pair $i,j\in[t]$ and an edge $(u,v)\in E(G)$ with $u\in C_{i}$ and $v\in C_{j}$ . By the problem definition, such an edge exists. We add edges $(u,x_{j})$ and $(v,x_{i})$ to $G^{\prime}$ .

Finally, the set $\{y_{1},y_{2},\ldots,y_{t}\}$ is made into a clique by adding all possible edges between them, and for every $i,j\in[t]$ , we add the edge $(x_{i},y_{j})$ in $G^{\prime}$ .

Construction of $H^{\prime}$ .

We start constructing $H^{\prime}$ from $G^{\prime}$ by deleting all vertices in $G$ in it. Formally, $V(H^{\prime})=\left(\bigcup_{i=1}^{t}S_{i}\right)\cup\left(\bigcup_{i=1}^{t}\{% x_{i},y_{i},z_{i}\}\right)$ , that is, it includes all newly introduced vertices from the sets $S_{i}$ and the auxiliary vertices $x_{i},y_{i},z_{i}$ for each $i\in[t]$ , but does not include any vertex from the original graph $G$ . The edge set of $H^{\prime}$ is defined as follows. First, a clique is formed on the vertex set $\{y_{1},y_{2},\ldots,y_{t}\}\cup\{x_{1},x_{2},\ldots,x_{t}\}$ , adding all edges between these vertices. Additionally, for every $i\in[t]$ , we include the edges $(x_{i},z_{i})$ and $(y_{i},z_{i})$ . Finally, for every $i\in[t]$ and each vertex $s\in S_{i}$ , we add the edge $(s,y_{i})$ .

This concludes the construction. We refer the reader to Figure 2 for an illustration of the reduction. We now prove the correctness of the reduction.

(a) Graph

G^{\prime}

.

(b) Graph

H^{\prime}

.

Figure 2: Illustration of the graphs

G^{\prime}

and

H^{\prime}

in the reduction for the lower bound of Theorem 1.

$(\Rightarrow)$ Suppose we are given a solution to the Sub-Cubic PVC instance, that is, a vertex cover $X\subseteq V(G)$ such that for every $i\in[t]$ , it holds that $|X\cap C_{i}|\leq k_{i}$ . We now describe a contraction sequence on $G^{\prime}$ that yields $H^{\prime}$ . For each partition $C_{i}\in\mathcal{P}$ , we proceed as follows: For every vertex $a\in X\cap C_{i}$ , we contract the edge $(a,x_{i})$ . For every vertex $b\in C_{i}\setminus X$ , we contract the edge $(b,y_{i})$ .

Observe that since $X$ is a vertex cover of $G$ , for each pair $i\neq j\in[t]$ , there exists exactly one edge in $G$ between $C_{i}$ and $C_{j}$ , say $(u,v)\in E(G)$ , with $u\in C_{i}$ and $v\in C_{j}$ . The contractions described above will result in $u$ being contracted to $x_{i}$ or $y_{i}$ , and $v$ to $x_{j}$ or $y_{j}$ . Since $u\in X$ or $v\in X$ , at least one of the endpoints is contracted to an $x$ -vertex, ensuring that each pair $(x_{i},x_{j})$ becomes adjacent in the resulting graph, thereby forming a clique on the set $\{x_{1},x_{2},\ldots,x_{t}\}$ .

Furthermore, for each $i\in[t]$ , since $|X\cap C_{i}|\leq k_{i}$ , it follows that no subset of $C_{i}$ of size $k_{i}+1$ is entirely mapped to $x_{i}$ . Therefore, for every vertex $s\in S_{i}$ , which corresponds to a subset of $C_{i}$ of size $k_{i}+1$ , at least one vertex in that subset is contracted to $y_{i}$ . Consequently, the edge $(s,y_{i})$ appears in the resulting graph, as required by $H^{\prime}$ . The edges $(x_{i},y_{i})$ and $(y_{i},z_{i})$ are preserved directly from the original construction. Thus, the contraction process yields graph $H^{\prime}$ , completing the forward direction of the reduction.
$(\Leftarrow)$ Suppose we are given a solution to the Labeled Contraction instance, i.e., a sequence of edge contractions that transforms $G^{\prime}$ into $H^{\prime}$ . We construct a corresponding solution $X\subseteq V(G)$ to the original Sub-Cubic PVC instance as follows.

Recall that the vertex set of $H^{\prime}$ is precisely $V(G^{\prime})\setminus V(G)$ , which implies that every contracted edge in the solution involves a vertex from $V(G)$ , more precisely vertices in $C_{i}$ for each $i\in[t]$ . Furthermore, observe that for each $i\in[t]$ , the vertices $z_{i}$ and those in $S_{i}$ do not share edges with each other or with vertices in $V(G)$ outside of $C_{i}$ neither in $G^{\prime}$ nor in $H^{\prime}$ . In particular, the absence of edges of the form $(z_{i},s)$ for any $s\in S_{i}$ , and the absence of edges $(z_{i},x_{j})$ or $(z_{i},y_{j})$ for $i\neq j$ , implies that vertices in $C_{i}$ can only be either contracted to $x_{i}$ or $y_{i}$ .

Now, for each vertex $s\in S_{i}$ , we note that $s$ is adjacent to $y_{i}$ in $H^{\prime}$ . In the construction of $G^{\prime}$ , the vertex $s$ was made adjacent to a subset $C_{i}^{\prime}\subseteq C_{i}$ of size $k_{i}+1$ . In order for $s$ to remain adjacent to $y_{i}$ in $H^{\prime}$ , it is necessary that at least one vertex in $C_{i}^{\prime}$ is contracted to $y_{i}$ . Thus, no subset of $C_{i}$ of size $k_{i}+1$ can be entirely contracted to $x_{i}$ . This ensures that at most $k_{i}$ vertices from $C_{i}$ are contracted to $x_{i}$ . Based on this observation, we define the vertex set $X\subseteq V(G)$ by including, for each $i\in[t]$ , all vertices in $C_{i}$ that are contracted to $x_{i}$ . From the argument above, we have $|X\cap C_{i}|\leq k_{i}$ for all $i\in[t]$ .

It remains to show that $X$ is a vertex cover of $G$ . Observe that in the construction of $G^{\prime}$ , for each pair $i,j\in[t]$ , $i\neq j$ , such that $E(G[C_{i}\cup C_{j}])\cap E(G)=\{(u,v)\}$ with $u\in C_{i}$ , $v\in C_{j}$ , we added edges $(u,x_{j})$ and $(v,x_{i})$ to $G^{\prime}$ . Since $x_{i}$ and $x_{j}$ are adjacent in $H^{\prime}$ , and since no edge directly connects $x_{i}$ and $x_{j}$ in $G^{\prime}$ , at least one of the vertices $u$ or $v$ must be contracted to $x_{i}$ or $x_{j}$ , respectively. This implies that either $u\in X$ or $v\in X$ , and hence $X$ intersects every edge in $E(G)$ . Therefore, $X$ is a valid vertex cover of $G$ . This completes the proof of correctness for the reduction.

To upper bound the treewidth of the graph $G^{\prime}$ , define the set $W=\{x_{i},y_{i},z_{i}\mid i\in[t]\}$ . Observe that the graph $G^{\prime}-W$ consists of $t$ vertex-disjoint subgraphs, each corresponding to a complete bipartite graph between $C_{i}$ and $S_{i}$ . For each $i\in[t]$ , the set $C_{i}$ is of size $\mathcal{O}(\sqrt{n})$ . This implies that the treewidth of each $G^{\prime}[C_{i}\cup S_{i}]$ is $\mathcal{O}(\sqrt{n})$ . Therefore, treewidth of $G^{\prime}$ is at most $\textsf{tw}(G^{\prime})\leq|W|+\max_{i\in[t]}\textsf{tw}(G^{\prime}[C_{i}\cup S% _{i}])=\mathcal{O}(\sqrt{n})$ .

Now suppose, for the sake of contradiction, that there exists an algorithm $\mathcal{A}$ that solves Labeled Contraction in time $2^{o(\textsf{tw}(G^{\prime})^{2})}\cdot|V(G^{\prime})|^{\mathcal{O}(1)}$ . We use $\mathcal{A}$ as a subroutine to construct an algorithm $\mathcal{B}$ for solving Sub-Cubic PVC. On input an instance $(G,\mathcal{P}=\{C_{1},C_{2},\ldots,C_{t}\},k_{1},\ldots,k_{t})$ of Sub-Cubic PVC with $n=|V(G)|$ , algorithm $\mathcal{B}$ performs the following steps: It constructs the corresponding instance $(G^{\prime},H^{\prime})$ of Labeled Contraction as described in the reduction. This step takes time $2^{\mathcal{O}(\sqrt{n})}$ . Then, it invoke algorithm $\mathcal{A}$ on the instance $(G^{\prime},H^{\prime})$ and return the result produced by $\mathcal{A}$ .

The correctness of algorithm $\mathcal{B}$ follows directly from the correctness of the reduction. Since $\textsf{tw}(G^{\prime})=\mathcal{O}(\sqrt{n})$ , the total running time of $\mathcal{B}$ is $2^{o(n)}$ , which contradicts the ETH, by Proposition 20. This establishes the claimed conditional lower bound stated in Theorem 1.

4 NP-hardness When Maximum Degree is Bounded

In this section, we establish the $\mathsf{NP}$ -hardness of the Labeled Contractibility problem, even when both the input graphs $G$ and $H$ have constant maximum degree. Specifically, we present a polynomial-time reduction from a variation of Positive-Not-All- $3$ -SAT problem to the Labeled Contractibility problem, thereby proving Theorem 2. We begin by formally defining the source problem, which is proved to be $\mathsf{NP}$ -complete in [22].

Positive-Not-All-

(3,4)

-SAT

Input: A $3$ -CNF Boolean formula $\psi$ in which every literal in each clause is positive and every variable appears in at most $4$ clauses.

Question: Does there exist a truth assignment to the variables such that every clause is satisfied and, in each clause, not all three literals are assigned True?

Let $\{x_{1},x_{2},\dots,x_{n}\}$ denote the set of variables, and let $\{C_{1},C_{2},\dots,C_{m}\}$ denote the set of clauses in the formula $\psi$ . Without loss of generality, assume that the number of clauses $m$ satisfies $2m+2=2^{q}$ for some integer $q$ ; let $p=2^{q}$ (note that $p$ is even).

We now describe the construction of two vertex-labeled graphs $G$ and $H$ corresponding to the given formula.

Construction of $𝑯$ .

Graph $H$ is a simple path on $p$ vertices $\{v_{1},v_{2},\ldots,v_{p}\}$ .

Construction of $𝑮$ .

We begin by constructing a complete binary tree of depth $q$ rooted at vertex $v_{1}$ , and later add some edges among its vertices. Note that the number of leaves of this binary tree is $2^{q}=2m+2$ . All but two leaves of this tree are labeled as $\{C_{1},a_{1},C_{2},a_{2},\dots,C_{m},a_{m}\}$ , alternating between clause vertices $C_{j}$ and auxiliary vertices $a_{j}$ . We label it such that $C_{i}$ and $a_{i}$ shares a parent. Consider the remaining two leaves which share a parent. Add an edge between these two leaves, label one of them as $v_{p/2}$ and other leave with any other label (as it will be irrelevant to the construction). We additionally add edges $(a_{i},a_{i+1})$ for all $i\in[m-1]$ . Now, consider the internal vertices of the constructed binary tree rooted at $v_{1}$ . Finally, along the shorted path between $v_{1}$ and $v_{p/2}$ , label the vertices as $v_{2},v_{3},\cdots,v_{p/2-1}$ respectively. For every $j\in[p/2-1]$ , let $U_{j}$ be the collection of vertices that are at exactly $j$ distance from $v_{1}$ . Alternately, these are all $2^{j}$ many vertices in $j^{th}$ -level of the complete binary tree. We add a path connecting these vertices. The internal structure of the tree, including its dummy vertices and edges, is constructed as illustrated in Figure 3.

A mirrored copy of this tree is constructed symmetrically, rooted at vertex $v_{p}$ , with the corresponding leaf labels $\{C_{1}^{\prime},a_{1}^{\prime},C_{2}^{\prime},a_{2}^{\prime},\dots,C_{m}^{% \prime},a_{m}^{\prime}\}$ , such that each primed vertex is associated with its unprimed counterpart. Additionally, we add the labels $v_{p/2+1},\cdots,v_{p}$ along the shortest path from $v_{p/2}$ to $v_{p}$ . Furthermore, we add an edge $(C_{j},C_{j}^{\prime})$ for each $j\in[m]$ , and an edge $(v_{p/2},v_{p/2+1})$ , thereby connecting the two binary trees via the central edge of the path. Finally, we add the edges $(a_{1},v_{p/2})$ and $(a_{1}^{\prime},v_{p/2+1})$ .

Variable Gadgets.

For each variable $x_{i}$ with $i\in[n]$ , introduce a new vertex $u_{i}$ . For each clause $C_{j}$ in which $x_{i}$ appears, connect $u_{i}$ to the vertices $\{C_{j},a_{j},C_{j}^{\prime},a_{j}^{\prime}\}$ .

This concludes the description of the reduction. Note that in the final graph $G$ , each vertex has degree at most $16$ .

For proof of the correctness, we refer the reader to the full version of this paper.

Figure 3: Example of the construction of

G

with

m=3

. We only show one

x_{i}

for convenience that appears in

C_{3}

.

5 Parameterized by Solution Size Plus Degeneracy

We prove Theorem 3 and Theorem 4 in the following two subsections.

5.1 Conditional Lower Bound

We remark that most of the previous reduction about Labeled Contraction are from the variation of 3-SAT problem called Not-All-Equal-3-SAT. In this variation, the input is a $3$ -CNF formula and the objective is to find an assignment that sets at least one but not all literals in every clause to set to True. We consider the following, different version of $3$ -SAT as starting point of our reduction and present a simple proof from 3-SAT to get desired conditional lower bound.

1

-in-

3

-SAT

Input: A Boolean formula $\psi$ in 3-CNF

Question: Does there exist a satisfying assignment such that exactly one literal is set to true in each clause?

Consider the following polynomial-time reduction from 3-SAT to 1-in-3-SAT where each clause $C^{i}=(x\lor\neg y\lor z)$ in the original formula is replaced by three clauses:

C^{i}_{1}=(\neg x\lor a_{i}\lor b_{i}),\quad C^{i}_{2}=(y\lor b_{i}\lor c_{i})% ,\quad C^{i}_{3}=(\neg z\lor c_{i}\lor d_{i}),

where $a_{i},b_{i},c_{i},d_{i}$ are fresh variables unique to the clause $C^{i}$ . This reduction introduces a linear blow-up in the number of variables and clauses. Combining this reduction with the (ETH) [37] and the Sparsification Lemma [38], we obtain the following:

Proposition 21.

Unless the ETH fails, $1$ -in- $3$ -SAT cannot be solved in time $2^{o(n+m)}$ , where $n$ and $m$ are the number of variables and clauses in the input formula, respectively.

We now reduce $1$ -in- $3$ -SAT to Labeled Contraction, ensuring that the number of vertices in $G$ and $H$ is linearly bounded by the number of variables and clauses in and instance of $1$ -in- $3$ -SAT.

We now proceed with the proof of Theorem 3.

Proof.

Let $\psi$ be an instance of $1$ -in- $3$ -SAT with variable set $\{x_{1},x_{2},\dots,x_{n}\}$ and clause set $\{C_{1},C_{2},\dots,C_{m}\}$ . We construct a corresponding instance $(G,H)$ of Labeled Contraction such that $\psi$ is satisfiable if and only if $H$ is a labeled contraction of $G$ .

We simultaneously define the graphs $G$ and $H$ as follows (See Figure 4 for an illustration.):

$\blacksquare$

Global vertices: Add two special vertices $g_{T}$ and $g_{F}$ to both $G$ and $H$ , connected by the edge $(g_{T},g_{F})$ . These represent the “true” and “false” assignments, respectively, for literals.
$\blacksquare$
Variable gadget: For each variable $x_{i}$ , $i\in[n]$ :
- –
  
  Add a vertex $u_{i}$ to both $G$ and $H$ , representing variable $x_{i}$ .
- –
  
  Add two vertices $v_{i}$ and $v^{\prime}_{i}$ to $G$ , corresponding to literals $x_{i}$ and $\neg x_{i}$ , respectively.
- –
  
  In $G$ , connect $u_{i}$ to both $v_{i}$ and $v^{\prime}_{i}$ . Also connect both $v_{i}$ and $v^{\prime}_{i}$ to $g_{T}$ and $g_{F}$ .
- –
  
  In $H$ , add edges $(u_{i},g_{T})$ , $(u_{i},g_{F})$ , and retain $(g_{T},g_{F})$ .
$\blacksquare$
Clause gadget: For each clause $C_{j}=(\ell_{j1}\lor\ell_{j2}\lor\ell_{j3})$ , let $\mathsf{litv}(\ell)$ denote $v_{i}$ if $\ell=x_{i}$ , and $v_{i}^{\prime}$ if $\ell=\neg x_{i}$ .
- –
  
  Add four vertices $w_{j0},w_{j1},w_{j2},w_{j3}$ to both $G$ and $H$ .
- –
  
  In $H$ , connect $w_{j0}$ to $g_{T}$ and $g_{F}$ .
- –
  
  In $G$ , connect $w_{j0}$ to $\mathsf{litv}(\ell_{j1})$ , $\mathsf{litv}(\ell_{j2})$ , and $\mathsf{litv}(\ell_{j3})$ .
- –
  
  For each $k\in\{1,2,3\}$ , add edge $(w_{jk},g_{T})$ to both $G$ and $H$ , and edge $(w_{jk},g_{F})$ only to $H$ .
- –
  
  Finally, form a 6-cycle in $G$ by connecting the three $w_{jk}$ ’s with the three $\mathsf{litv}(\ell_{jk})$ ’s in an alternating cycle such that no two $w_{jk}$ ’s nor any two $\mathsf{litv}(\ell_{jk})$ ’s are adjacent.

This completes the reduction. It is easy to see that it takes polynomial time, and both graphs $G$ and $H$ have degeneracy at most $3$ .

(a) Variable gadget in

G

.

(b) Variable gadget in

H

.

(c) Clause gadget in

G

.

(d) Clause gadget in

H

.

Figure 4: Illustration of the reduction. (Top) Variable gadgets in

G

and

H

for a variable

(v_{i})

. (Bottom) Clause gadgets in

G

and

H

for some clause of the form

(v_{i}\lor v_{j}\lor v_{k}^{\prime})

.

We now show the equivalence between satisfiability of $\psi$ and labeled contractibility of $G$ into $H$ .
( $\Rightarrow$ ) Suppose there exists a satisfying assignment $\alpha:\{x_{1},\dots,x_{n}\}\to\{\texttt{True},\texttt{False}\}$ such that exactly one literal is true in each clause. Define the contraction sequence $S$ as follows:

$\blacksquare$

For each $x_{i}$ , if $\alpha(x_{i})=\texttt{True}$ , then add edges $(v_{i},g_{T})$ , $(v_{i}^{\prime},g_{F})$ to $S$ ; and if $\alpha(x_{i})=\texttt{False}$ , then add edges $(v_{i},g_{F})$ , $(v_{i}^{\prime},g_{T})$ to $S$ .

This ensures the correct neighborhood for $u_{i}$ in $H$ , as it will have edges to both $g_{T}$ and $g_{F}$ .

Now consider any clause $C_{j}$ . Since exactly one literal is true under $\alpha$ , exactly one $\mathsf{litv}(\ell_{jk})$ is contracted into $g_{T}$ , and the remaining two are contracted into $g_{F}$ . The contraction of the $w_{jk}$ -triangle via the 6-cycle then ensures:

$\blacksquare$

The edge $(w_{j0},g_{T})$ is introduced by the literal assigned true;
$\blacksquare$

The edge $(w_{j0},g_{F})$ is introduced by the literals assigned false;
$\blacksquare$

All three edges $(g_{F},w_{j1}),(g_{F},w_{j2}),(g_{F},w_{j3})$ are created.

Hence, the resulting graph after the contraction is precisely $H$ .
( $\Leftarrow$ ) Conversely, suppose $H$ is a labeled contraction of $G$ . We argue that this implies a satisfying assignment for $\psi$ .

The only way to create both edges $(u_{i},g_{T})$ and $(u_{i},g_{F})$ in $H$ is by contracting $v_{i}$ and $v_{i}^{\prime}$ into $g_{T}$ and $g_{F}$ , respectively, or vice versa. This naturally defines a valid assignment:

\alpha(x_{i})=\begin{cases}\texttt{True}&\text{if }v_{i}\text{ is contracted % to }g_{T},\\ \texttt{False}&\text{if }v_{i}^{\prime}\text{ is contracted to }g_{T}.\end{cases}

Next, observe that to produce all three edges $(g_{F},w_{j1}),(g_{F},w_{j2}),(g_{F},w_{j3})$ , at least two of the literals in clause $C_{j}$ must contract to $g_{F}$ , while one contracts to $g_{T}$ . Thus, in each clause, exactly one literal must be set to true under $\alpha$ . Therefore, $\alpha$ satisfies $\psi$ as a 1-in-3-SAT assignment.

Each vertex in the variable and clause gadgets has degree at most 3 in $G$ and at most 2 in $H$ , so the degeneracy of both graphs is bounded by a constant. The size of $G$ is linear in $n+m$ , and the construction can be completed in polynomial time. Hence, if Labeled Contraction can be solved in time $2^{o(|V(G)|+|E(G)|)}$ , then 1-in-3-SAT can be solved in time $2^{o(n+m)}$ , which contradicts ETH according to Proposition 21. This completes the proof of Theorem 3. $\hfill\blacktriangleleft$

5.2 Algorithmic Result

We first present proof of Theorem 4 establishing an alternate $\mathsf{FPT}$ algorithm and later mention its consequences. Recall that the theorem states that the Labeled Contraction problem admits an algorithm with running time $(\delta(H)+1)^{k}\cdot|V(G)|^{\mathcal{O}(1)}$ , where $k=|V(G)\setminus V(H)|$ .

Let $(G,H)$ be an instance of the Labeled Contraction problem. With sanity check, we can assume that $V(H)\subseteq V(G)$ .

The goal is to decide whether there exists a valid witness structure $\mathcal{W}=\{W_{h}\subseteq V(G)\mid h\in V(H)\}$ such that contracting each $W_{h}$ into the vertex $h$ yields the graph $H$ .

Let $k=|V(G)\setminus V(H)|$ denote the number of vertices in $G$ that are not in $H$ , and hence must be contracted. Each such vertex $x\in V(G)\setminus V(H)$ must be assigned to exactly one vertex $h\in V(H)$ , corresponding to the witness set $W_{h}$ into which $x$ will be contracted.

Define a mapping $\phi:V(G)\to V(H)$ as follows: $(i)$ For each $v\in V(H)$ , set $\phi(v)=v$ ; $(ii)$ For each $x\in V(G)\setminus V(H)$ , $\phi(x)$ denotes the vertex in $V(H)$ to which $x$ is assigned (i.e., the representative vertex of the witness set containing $x$ ). A mapping $\phi$ defines a candidate witness structure, and we wish to determine whether it corresponds to a valid contraction of $G$ into $H$ .

To bound the number of candidate functions $\phi$ , we exploit structural properties of the graph $H$ . Let $\delta(H)$ denote the degeneracy of $H$ . By definition, $H$ admits an ordering $v_{1},v_{2},\ldots,v_{n}$ such that each vertex has at most $\delta(H)$ neighbors among its predecessors. This implies that $H$ is $(\delta(H)+1)$ -colorable, and such a coloring can be computed in polynomial time.

Fix a proper coloring $c:V(H)\to[\delta(H)+1]$ . For each vertex $x\in V(G)\setminus V(H)$ , let $N_{H}(x):=\{v\in V(H)\mid\{x,v\}\in E(G)\}$ . If two vertices $y_{1},y_{2}\in N_{H}(x)$ belong to the same color class (i.e., $c(y_{1})=c(y_{2})$ ) and $\{y_{1},y_{2}\}\notin E(H)$ , then assigning $x$ to either $y_{1}$ or $y_{2}$ would result in the edge $\{y_{1},y_{2}\}$ being introduced during the contraction process – contradicting the assumption that $H$ is the target graph. Therefore, for each $x\in V(G)\setminus V(H)$ , there are at most $\delta(H)+1$ valid choices for $\phi(x)$ . These choices corresponds at most one vertex in each color class. Thus, the total number of candidate assignments $\phi$ is bounded by $(\delta(H)+1)^{k}$ . For each such assignment, we can verify in polynomial time whether the induced contraction yields $H$ , by simulating the contraction and checking edge and label consistency. This yields an algorithm with running time $(\delta(H)+1)^{k}\cdot|V(G)|^{\mathcal{O}(1)}$ . This completes the proof for Theorem 4

6 Brute-force Algorithm and its Optimality

We now prove Theorem 5. We establish a conditional lower bound showing that the brute-force algorithm described in the full version is essentially optimal, unless the Exponential Time Hypothesis (ETH) fails. For the full details of the brute-force algorithm and its exact running time analysis, we refer the reader to the longer version of this paper. We present the conditional lower bound proof here.

Our lower bound is derived via a polynomial-time reduction from the following problem, introduced by Fomin et al. [28], which has served as a hardness source for several contraction-based graph problems.

Cross Matching

Input: A graph $G^{\prime}$ together with a partition $(A,B)$ of $V(G^{\prime})$ such that $|A|=|B|$ .

Question: Does there exist a perfect matching $M\subseteq E(G^{\prime})$ such that each edge in $M$ connects one vertex from $A$ and one from $B$ , and the graph $G^{\prime}/M$ is a clique?

Proposition 22 (Lemma 4.1 in [28]).

Unless the ETH fails, Cross Matching cannot be solved in time $n^{o(n)}$ , where $n=|A|=|B|$ .

We now present a polynomial-time reduction from Cross Matching to Labeled Contractibility, preserving the ETH-based lower bound under size-preserving transformation.

(a) Graph

G

.

(b) Graph

H

.

Figure 5: Illustration of the graphs

G

and

H

in the reduction. The required adjacency across

\{x_{1},x_{2}\}

and

A

forces a candidate solution to form a matching across

A

and

B

.

Lemma 23.

Unless the ETH fails, the Labelled Contractibility problem does not admit an algorithm running in time $|V(H)|^{o(|V(G)|)}$ .

Proof.

Let $(G^{\prime},A,B)$ be an instance of Cross Matching with $|A|=|B|=n$ . We construct an equivalent instance $(G,H)$ of Labeled Contractibility as follows.

The graph $G$ is obtained from $G^{\prime}$ by introducing two new vertices $x_{1}$ and $x_{2}$ , and adding edges between each of these new vertices and all vertices in $B$ . Formally, $V(G)=V(G^{\prime})\cup\{x_{1},x_{2}\}$ , and $E(G)=E(G^{\prime})\cup\{(x_{1},b),(x_{2},b)\mid b\in B\}$ . The target graph $H$ is defined on vertex set $V(H)=A\cup\{x_{1},x_{2}\}$ , with the following edge set: $(i)$ all pairs $\{a_{1},a_{2}\}\subseteq A$ are adjacent (i.e., $A$ induces a clique); and $(ii)$ both $x_{1}$ and $x_{2}$ are adjacent to every vertex in $A$ . We remark that vertices $x_{1}$ and $x_{2}$ are not adjacent. Equivalently, $H$ is a complete graph on $A\cup\{x_{1},x_{2}\}$ minus the edge $(x_{1},x_{2})$ . See Figure 5 for an illustration.

We prove that $(G^{\prime},A,B)$ is a Yes-instance of Cross Matching if and only if $(G,H)$ is a Yes-instance of Labeled Contractibility.

( $\Rightarrow$ ) Suppose $(G^{\prime},A,B)$ is a Yes-instance of Cross Matching. Then there exists a perfect matching $M$ between $A$ and $B$ such that the contracted graph $G^{\prime}/M$ is a clique.

We construct a labeled contraction sequence $S$ on $G$ by contracting each edge $(a,b)\in M$ , with $a\in A$ and $b\in B$ , in arbitrary order. Since $M$ is a matching, all contracted edges are vertex-disjoint. After performing all contractions in $S$ , each vertex $b\in B$ is removed, and the vertex set of $G/S$ becomes $A\cup\{x_{1},x_{2}\}$ .

In $G/S$ , the subgraph induced by $A$ is a clique, since $G^{\prime}/M$ is a clique and the contractions only merged $b$ into $a$ . Furthermore, since $x_{1}$ and $x_{2}$ were connected to every $b\in B$ , and each $b$ was contracted into some $a\in A$ , the contraction introduces edges from both $x_{1}$ and $x_{2}$ to every $a\in A$ . However, since $x_{1}$ and $x_{2}$ are not adjacent to each other in the original graph $G$ , and no contraction involved either of them, the edge $(x_{1},x_{2})$ is not introduced. Thus, the resulting graph $G/S$ is $H$ .

( $\Leftarrow$ ) Suppose $(G,H)$ is a Yes-instance of Labelled Contractibility, i.e., there exists a sequence $S$ of labeled contractions such that $G/S=H$ .

By construction, $V(G)=A\cup B\cup\{x_{1},x_{2}\}$ and $V(H)=A\cup\{x_{1},x_{2}\}$ . Therefore, all vertices in $B$ must be removed during the contraction sequence. In the labeled contraction model, a vertex is removed only when it is the second vertex in a contracted pair. Hence, each $b\in B$ must appear as the second vertex in some contraction $(u,b)\in S$ .

We now argue that each $b\in B$ must be contracted into a distinct vertex $a\in A$ . Suppose, for contradiction, that some $a\in A$ does not serve as the representative of any contracted pair. Consider the edge $(a,x_{1})$ in $H$ . Since $a$ and $x_{1}$ were not adjacent in $G$ , this edge must have been created through a contraction involving a common neighbor $b\in B$ . The only way to generate such an edge is to contract $b$ into $x_{1}$ , i.e., perform $(x_{1},b)\in S$ . However, $b$ is also adjacent to $x_{2}$ in $G$ , and contracting $b$ into $x_{1}$ would create an edge $(x_{1},x_{2})$ , a contradiction, since $(x_{1},x_{2})\notin E(H)$ . Therefore, for each $a\in A$ , there must be a distinct $b\in B$ such that $(a,b)\in S$ . Since $|A|=|B|=n$ , this yields a perfect matching $M=\{(a,b)\in S\}$ between $A$ and $B$ .

Finally, we argue that $G^{\prime}/M$ is a clique. Since $G/S=H$ , and the subgraph induced by $A$ in $H$ is a clique, the same must hold in $G^{\prime}/M$ (as contractions outside $A\cup B$ do not affect this subgraph). Thus, $(G^{\prime},A,B)$ is a Yes-instance of Cross Matching.

The construction of $(G,H)$ from $(G^{\prime},A,B)$ takes polynomial time. The sizes satisfy $|V(G)|=2n+2$ and $|V(H)|=n+2$ , both in $\mathcal{O}(n)$ . Therefore, if Labeled Contractibility admitted an algorithm running in time $|V(H)|^{o(|V(G)|)}$ , then Cross Matching could be solved in time $n^{o(n)}$ , contradicting the ETH according to Proposition 22. This concludes the proof of the lemma. $\hfill\blacktriangleleft$

References

[1] Akanksha Agarwal, Saket Saurabh, and Prafullkumar Tale. On the parameterized complexity of contraction to generalization of trees. Theory of Computing Systems, 63(3):587–614, 2019. doi:10.1007/s00224-018-9892-z.
[2] Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh, and Prafullkumar Tale. Paths to trees and cacti. Theoretical Computer Science, 860:98–116, 2021. doi:10.1016/j.tcs.2021.01.033.
[3] Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split contraction: The untold story. ACM Transactions on Computation Theory, 11(3):1–22, 2019. doi:10.1145/3319909.
[4] Takao Asano and Tomio Hirata. Edge-contraction problems. J. Comput. Syst. Sci., 26(2):197–208, 1983. doi:10.1016/0022-0000(83)90012-0.
[5] Rémy Belmonte, Petr A. Golovach, Pim Hof, and Daniël Paulusma. Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica, 51(7):473–497, 2014. doi:10.1007/S00236-014-0204-Z.
[6] Benjamin Bergougnoux, Tuukka Korhonen, and Jesper Nederlof. Tight lower bounds for problems parameterized by rank-width. arXiv preprint, 2210(02117), 2022. doi:10.48550/arXiv.2210.02117.
[7] Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michal Pilipczuk. A subexponential parameterized algorithm for proper interval completion. SIAM J. Discret. Math., 29(4):1961–1987, 2015. doi:10.1137/140988565.
[8] Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michal Pilipczuk. Subexponential parameterized algorithm for interval completion. ACM Trans. Algorithms, 14(3):35:1–35:62, 2018. doi:10.1145/3186896.
[9] Andries E. Brouwer and Henk Jan Veldman. Contractibility and np-completeness. J. Graph Theory, 11(1):71–79, 1987. doi:10.1002/jgt.3190110111.
[10] Leizhen Cai and Chengwei Guo. Contracting few edges to remove forbidden induced subgraphs. In Proc. of the 8th International Symposium on Parameterized and Exact Computation (IPEC), volume 8246 of LNCS, pages 97–109, 2013. doi:10.1007/978-3-319-03898-8_10.
[11] Yixin Cao. Linear recognition of almost interval graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 1096–1115. SIAM, 2016. doi:10.1137/1.9781611974331.ch77.
[12] Yixin Cao. Unit interval editing is fixed-parameter tractable. Inf. Comput., 253:109–126, 2017. doi:10.1016/j.ic.2017.01.008.
[13] Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms, 11(3):21:1–21:35, 2015. doi:10.1145/2629595.
[14] Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118–137, 2016. doi:10.1007/s00453-015-0014-x.
[15] Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, and Prafullkumar Tale. Parameterized complexity of isometric path partition: treewidth and diameter. arXiv preprint, 2508(05448), 2025. doi:10.48550/arXiv.2508.05448.
[16] Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, and Prafullkumar Tale. Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover. 35th International Symposium on Algorithms and Computation (ISAAC 2024), 322:19:1–19:18, 2024. doi:10.4230/LIPIcs.ISAAC.2024.19.
[17] Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification. CoRR, abs/2001.06867, 2020. arXiv:2001.06867.
[18] Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification, 2020. arXiv:2001.06867.
[19] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[20] Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput., 256:62–82, 2017. doi:10.1016/J.IC.2017.04.009.
[21] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. ACM Trans. Algorithms, 18(2):17:1–17:31, 2022. doi:10.1145/3506707.
[22] Andreas Darmann and Janosch Döcker. On a simple hard variant of not-all-equal 3-sat. Theor. Comput. Sci., 815:147–152, 2020. doi:10.1016/J.TCS.2020.02.010.
[23] Pål Grønås Drange, Markus Fanebust Dregi, Daniel Lokshtanov, and Blair D. Sullivan. On the threshold of intractability. J. Comput. Syst. Sci., 124:1–25, 2022. doi:10.1016/j.jcss.2021.09.003.
[24] Pål Grønås Drange, Fedor V. Fomin, Michal Pilipczuk, and Yngve Villanger. Exploring subexponential parameterized complexity of completion problems. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS), volume 25 of LIPIcs, pages 288–299, 2014. doi:10.4230/LIPIcs.STACS.2014.288.
[25] Pål Grønås Drange and Michal Pilipczuk. A polynomial kernel for trivially perfect editing. Algorithmica, 80(12):3481–3524, 2018. doi:10.1007/s00453-017-0401-6.
[26] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. doi:10.1007/3-540-29953-X.
[27] Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Yngve Villanger. Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J. Comput. Syst. Sci., 80(7):1430–1447, 2014. doi:10.1016/j.jcss.2014.04.015.
[28] Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. Computation of hadwiger number and related contraction problems: Tight lower bounds. ACM Trans. Comput. Theory, 13(2):10:1–10:25, 2021. doi:10.1145/3448639.
[29] Fedor V. Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput., 42(6):2197–2216, 2013. doi:10.1137/11085390X.
[30] Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In 51st International Colloquium on Automata, Languages, and Programming, ICALP, volume 297 of LIPIcs, pages 66:1–66:19, 2024. doi:10.4230/LIPICS.ICALP.2024.66.
[31] Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric dimension and geodetic set parameterized by vertex cover. In 42nd International Symposium on Theoretical Aspects of Computer Science, STACS, volume 327 of LIPIcs, pages 33:1–33:20, 2025. doi:10.4230/LIPICS.STACS.2025.33.
[32] Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, and Dimitrios M Thilikos. Increasing the minimum degree of a graph by contractions. Theoretical Computer Science, 481:74–84, 2013. doi:10.1016/j.tcs.2013.02.030.
[33] Petr A. Golovach, Pim van’t Hof, and Daniël Paulusma. Obtaining planarity by contracting few edges. Theoretical Computer Science, 476:38–46, 2013. doi:10.1016/j.tcs.2012.12.041.
[34] Sylvain Guillemot and Dániel Marx. A faster FPT algorithm for Bipartite Contraction. Information Processing Letters, 113(22):906–912, 2013. doi:10.1016/j.ipl.2013.09.004.
[35] Pinar Heggernes, Pim van ’t Hof, Benjamin Lévêque, Daniel Lokshtanov, and Christophe Paul. Contracting graphs to paths and trees. Algorithmica, 68(1):109–132, 2014. doi:10.1007/s00453-012-9670-2.
[36] Pinar Heggernes, Pim van ’t Hof, Daniel Lokshtanov, and Christophe Paul. Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics, 27(4):2143–2156, 2013. doi:10.1137/130907392.
[37] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367–375, 2001. doi:10.1006/JCSS.2000.1727.
[38] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001. doi:10.1006/JCSS.2001.1774.
[39] Tuukka Korhonen and Daniel Lokshtanov. An improved parameterized algorithm for treewidth. SIAM Journal on Computing, 0(0):STOC23–155–STOC23–214, 2023. doi:10.1137/23M1595059.
[40] R. Krithika, Pranabendu Misra, and Prafullkumar Tale. A single exponential-time FPT algorithm for cactus contraction. Theor. Comput. Sci., 954:113803, 2023. doi:10.1016/J.TCS.2023.113803.
[41] Manuel Lafond and Bertrand Marchand. The parameterized landscape of labeled graph contractions. In (To appear) in Algorithms and Data Structures Symposium WADS 2025, volume abs/2502.16096, 2025. doi:10.48550/arXiv.2502.16096.
[42] John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. J. Comput. Syst. Sci., 20(2):219–230, 1980. doi:10.1016/0022-0000(80)90060-4.
[43] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM J. Comput., 47(3):675–702, 2018. doi:10.1137/16M1104834.
[44] Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. On the hardness of eliminating small induced subgraphs by contracting edges. In Proc. of the 8th International Symposium on Parameterized and Exact Computation (IPEC), volume 8246 of LNCS, pages 243–254, 2013. doi:10.1007/978-3-319-03898-8_21.
[45] Bertrand Marchand, Nadia Tahiri, Olivier Tremblay Savard, and Manuel Lafond. Finding maximum common contractions between phylogenetic networks. In Solon P. Pissis and Wing-Kin Sung, editors, 24th International Workshop on Algorithms in Bioinformatics, WABI, volume 312 of LIPIcs, pages 16:1–16:24, 2024. doi:10.4230/LIPICS.WABI.2024.16.
[46] Bertrand Marchand, Nadia Tahiri, Olivier Tremblay-Savard, and Manuel Lafond. Finding Maximum Common Contractions Between Phylogenetic Networks. In WABI, pages 16:1–16:24, 2024. doi:10.4230/LIPIcs.WABI.2024.16.
[47] Barnaby Martin and Daniël Paulusma. The computational complexity of disconnected cut and $2K_{2}$ -partition. Journal of Combinatorial Theory, Series B, 111:17–37, 2015. doi:10.1016/j.jctb.2014.09.002.
[48] Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS, volume 6907 of Lecture Notes in Computer Science, pages 520–531. Springer, 2011. doi:10.1007/978-3-642-22993-0_47.
[49] Ignasi Sau and Uéverton dos Santos Souza. Hitting forbidden induced subgraphs on bounded treewidth graphs. Inf. Comput., 281:104812, 2021. doi:10.1016/J.IC.2021.104812.
[50] Saket Saurabh and Prafullkumar Tale. On the parameterized complexity of maximum degree contraction problem. arXiv preprint arXiv:2009.11793, 2020.
[51] Saket Saurabh and Prafullkumar Tale. On the parameterized complexity of maximum degree contraction problem. In Proc. of the 15th International Symposium on Parameterized and Exact Computation (IPEC), volume 180 of LIPIcs, pages 26:1–26:16, 2020. doi:10.4230/LIPIcs.IPEC.2020.26.
[52] Prafullkumar Tale. Double exponential lower bound for telephone broadcast, 2024. doi:10.48550/arXiv.2403.03501.
[53] Toshimasa Watanabe, Tadashi Ae, and Akira Nakamura. On the removal of forbidden graphs by edge-deletion or by edge-contraction. Discret. Appl. Math., 3(2):151–153, 1981. doi:10.1016/0166-218X(81)90039-1.
[54] Mihalis Yannakakis. Node- and Edge-Deletion NP-Complete Problems. In Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 253–264, 1978. doi:10.1145/800133.804355.

[bib.bib1] [1] Akanksha Agarwal, Saket Saurabh, and Prafullkumar Tale. On the parameterized complexity of contraction to generalization of trees. Theory of Computing Systems, 63(3):587–614, 2019. doi:10.1007/s00224-018-9892-z.

[bib.bib2] [2] Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh, and Prafullkumar Tale. Paths to trees and cacti. Theoretical Computer Science, 860:98–116, 2021. doi:10.1016/j.tcs.2021.01.033.

[bib.bib3] [3] Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split contraction: The untold story. ACM Transactions on Computation Theory, 11(3):1–22, 2019. doi:10.1145/3319909.

[bib.bib4] [4] Takao Asano and Tomio Hirata. Edge-contraction problems. J. Comput. Syst. Sci., 26(2):197–208, 1983. doi:10.1016/0022-0000(83)90012-0.

[bib.bib5] [5] Rémy Belmonte, Petr A. Golovach, Pim Hof, and Daniël Paulusma. Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica, 51(7):473–497, 2014. doi:10.1007/S00236-014-0204-Z.

[bib.bib6] [6] Benjamin Bergougnoux, Tuukka Korhonen, and Jesper Nederlof. Tight lower bounds for problems parameterized by rank-width. arXiv preprint, 2210(02117), 2022. doi:10.48550/arXiv.2210.02117.

[bib.bib7] [7] Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michal Pilipczuk. A subexponential parameterized algorithm for proper interval completion. SIAM J. Discret. Math., 29(4):1961–1987, 2015. doi:10.1137/140988565.

[bib.bib8] [8] Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michal Pilipczuk. Subexponential parameterized algorithm for interval completion. ACM Trans. Algorithms, 14(3):35:1–35:62, 2018. doi:10.1145/3186896.

[bib.bib9] [9] Andries E. Brouwer and Henk Jan Veldman. Contractibility and np-completeness. J. Graph Theory, 11(1):71–79, 1987. doi:10.1002/jgt.3190110111.

[bib.bib10] [10] Leizhen Cai and Chengwei Guo. Contracting few edges to remove forbidden induced subgraphs. In Proc. of the 8th International Symposium on Parameterized and Exact Computation (IPEC), volume 8246 of LNCS, pages 97–109, 2013. doi:10.1007/978-3-319-03898-8_10.

[bib.bib11] [11] Yixin Cao. Linear recognition of almost interval graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 1096–1115. SIAM, 2016. doi:10.1137/1.9781611974331.ch77.

[bib.bib12] [12] Yixin Cao. Unit interval editing is fixed-parameter tractable. Inf. Comput., 253:109–126, 2017. doi:10.1016/j.ic.2017.01.008.

[bib.bib13] [13] Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms, 11(3):21:1–21:35, 2015. doi:10.1145/2629595.

[bib.bib14] [14] Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118–137, 2016. doi:10.1007/s00453-015-0014-x.

[bib.bib15] [15] Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, and Prafullkumar Tale. Parameterized complexity of isometric path partition: treewidth and diameter. arXiv preprint, 2508(05448), 2025. doi:10.48550/arXiv.2508.05448.

[bib.bib16] [16] Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, and Prafullkumar Tale. Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover. 35th International Symposium on Algorithms and Computation (ISAAC 2024), 322:19:1–19:18, 2024. doi:10.4230/LIPIcs.ISAAC.2024.19.

[bib.bib17] [17] Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification. CoRR, abs/2001.06867, 2020. arXiv:2001.06867.

[bib.bib18] [18] Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification, 2020. arXiv:2001.06867.

[bib.bib19] [19] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib20] [20] Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput., 256:62–82, 2017. doi:10.1016/J.IC.2017.04.009.

[bib.bib21] [21] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. ACM Trans. Algorithms, 18(2):17:1–17:31, 2022. doi:10.1145/3506707.

[bib.bib22] [22] Andreas Darmann and Janosch Döcker. On a simple hard variant of not-all-equal 3-sat. Theor. Comput. Sci., 815:147–152, 2020. doi:10.1016/J.TCS.2020.02.010.

[bib.bib23] [23] Pål Grønås Drange, Markus Fanebust Dregi, Daniel Lokshtanov, and Blair D. Sullivan. On the threshold of intractability. J. Comput. Syst. Sci., 124:1–25, 2022. doi:10.1016/j.jcss.2021.09.003.

[bib.bib24] [24] Pål Grønås Drange, Fedor V. Fomin, Michal Pilipczuk, and Yngve Villanger. Exploring subexponential parameterized complexity of completion problems. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS), volume 25 of LIPIcs, pages 288–299, 2014. doi:10.4230/LIPIcs.STACS.2014.288.

[bib.bib25] [25] Pål Grønås Drange and Michal Pilipczuk. A polynomial kernel for trivially perfect editing. Algorithmica, 80(12):3481–3524, 2018. doi:10.1007/s00453-017-0401-6.

[bib.bib26] [26] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. doi:10.1007/3-540-29953-X.

[bib.bib27] [27] Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Yngve Villanger. Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J. Comput. Syst. Sci., 80(7):1430–1447, 2014. doi:10.1016/j.jcss.2014.04.015.

[bib.bib28] [28] Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. Computation of hadwiger number and related contraction problems: Tight lower bounds. ACM Trans. Comput. Theory, 13(2):10:1–10:25, 2021. doi:10.1145/3448639.

[bib.bib29] [29] Fedor V. Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput., 42(6):2197–2216, 2013. doi:10.1137/11085390X.

[bib.bib30] [30] Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In 51st International Colloquium on Automata, Languages, and Programming, ICALP, volume 297 of LIPIcs, pages 66:1–66:19, 2024. doi:10.4230/LIPICS.ICALP.2024.66.

[bib.bib31] [31] Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric dimension and geodetic set parameterized by vertex cover. In 42nd International Symposium on Theoretical Aspects of Computer Science, STACS, volume 327 of LIPIcs, pages 33:1–33:20, 2025. doi:10.4230/LIPICS.STACS.2025.33.

[bib.bib32] [32] Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, and Dimitrios M Thilikos. Increasing the minimum degree of a graph by contractions. Theoretical Computer Science, 481:74–84, 2013. doi:10.1016/j.tcs.2013.02.030.

[bib.bib33] [33] Petr A. Golovach, Pim van’t Hof, and Daniël Paulusma. Obtaining planarity by contracting few edges. Theoretical Computer Science, 476:38–46, 2013. doi:10.1016/j.tcs.2012.12.041.

[bib.bib34] [34] Sylvain Guillemot and Dániel Marx. A faster FPT algorithm for Bipartite Contraction. Information Processing Letters, 113(22):906–912, 2013. doi:10.1016/j.ipl.2013.09.004.

[bib.bib35] [35] Pinar Heggernes, Pim van ’t Hof, Benjamin Lévêque, Daniel Lokshtanov, and Christophe Paul. Contracting graphs to paths and trees. Algorithmica, 68(1):109–132, 2014. doi:10.1007/s00453-012-9670-2.

[bib.bib36] [36] Pinar Heggernes, Pim van ’t Hof, Daniel Lokshtanov, and Christophe Paul. Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics, 27(4):2143–2156, 2013. doi:10.1137/130907392.

[bib.bib37] [37] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367–375, 2001. doi:10.1006/JCSS.2000.1727.

[bib.bib38] [38] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001. doi:10.1006/JCSS.2001.1774.

[bib.bib39] [39] Tuukka Korhonen and Daniel Lokshtanov. An improved parameterized algorithm for treewidth. SIAM Journal on Computing, 0(0):STOC23–155–STOC23–214, 2023. doi:10.1137/23M1595059.

[bib.bib40] [40] R. Krithika, Pranabendu Misra, and Prafullkumar Tale. A single exponential-time FPT algorithm for cactus contraction. Theor. Comput. Sci., 954:113803, 2023. doi:10.1016/J.TCS.2023.113803.

[bib.bib41] [41] Manuel Lafond and Bertrand Marchand. The parameterized landscape of labeled graph contractions. In (To appear) in Algorithms and Data Structures Symposium WADS 2025, volume abs/2502.16096, 2025. doi:10.48550/arXiv.2502.16096.

[bib.bib42] [42] John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. J. Comput. Syst. Sci., 20(2):219–230, 1980. doi:10.1016/0022-0000(80)90060-4.

[bib.bib43] [43] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM J. Comput., 47(3):675–702, 2018. doi:10.1137/16M1104834.

[bib.bib44] [44] Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. On the hardness of eliminating small induced subgraphs by contracting edges. In Proc. of the 8th International Symposium on Parameterized and Exact Computation (IPEC), volume 8246 of LNCS, pages 243–254, 2013. doi:10.1007/978-3-319-03898-8_21.

[bib.bib45] [45] Bertrand Marchand, Nadia Tahiri, Olivier Tremblay Savard, and Manuel Lafond. Finding maximum common contractions between phylogenetic networks. In Solon P. Pissis and Wing-Kin Sung, editors, 24th International Workshop on Algorithms in Bioinformatics, WABI, volume 312 of LIPIcs, pages 16:1–16:24, 2024. doi:10.4230/LIPICS.WABI.2024.16.

[bib.bib46] [46] Bertrand Marchand, Nadia Tahiri, Olivier Tremblay-Savard, and Manuel Lafond. Finding Maximum Common Contractions Between Phylogenetic Networks. In WABI, pages 16:1–16:24, 2024. doi:10.4230/LIPIcs.WABI.2024.16.

[bib.bib47] [47] Barnaby Martin and Daniël Paulusma. The computational complexity of disconnected cut and $2K_{2}$ -partition. Journal of Combinatorial Theory, Series B, 111:17–37, 2015. doi:10.1016/j.jctb.2014.09.002.

[bib.bib48] [48] Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS, volume 6907 of Lecture Notes in Computer Science, pages 520–531. Springer, 2011. doi:10.1007/978-3-642-22993-0_47.

[bib.bib49] [49] Ignasi Sau and Uéverton dos Santos Souza. Hitting forbidden induced subgraphs on bounded treewidth graphs. Inf. Comput., 281:104812, 2021. doi:10.1016/J.IC.2021.104812.

[bib.bib50] [50] Saket Saurabh and Prafullkumar Tale. On the parameterized complexity of maximum degree contraction problem. arXiv preprint arXiv:2009.11793, 2020.

[bib.bib51] [51] Saket Saurabh and Prafullkumar Tale. On the parameterized complexity of maximum degree contraction problem. In Proc. of the 15th International Symposium on Parameterized and Exact Computation (IPEC), volume 180 of LIPIcs, pages 26:1–26:16, 2020. doi:10.4230/LIPIcs.IPEC.2020.26.

[bib.bib52] [52] Prafullkumar Tale. Double exponential lower bound for telephone broadcast, 2024. doi:10.48550/arXiv.2403.03501.

[bib.bib53] [53] Toshimasa Watanabe, Tadashi Ae, and Akira Nakamura. On the removal of forbidden graphs by edge-deletion or by edge-contraction. Discret. Appl. Math., 3(2):151–153, 1981. doi:10.1016/0166-218X(81)90039-1.

[bib.bib54] [54] Mihalis Yannakakis. Node- and Edge-Deletion NP-Complete Problems. In Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 253–264, 1978. doi:10.1145/800133.804355.

A Finer View of the Parameterized Landscape of Labeled Graph Contractions

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

Theorem 2.

Theorem 3.

Theorem 4.

Theorem 5.

Organization.

2 Preliminaries

Definition 6.

Definition 7.

3 Parameterized by Treewidth

Theorem 1. [Restated, see original statement.]

3.1 Algorithmic Result

Definition 8 ([19]).

Definition 9 ([19]).

Lemma 10 ([41], Lemma 13).

3.1.1 Witness Structures and Functional Representation

Definition 11 (Parent function).

Definition 12 (Originator function).

Definition 13 (Witness impression).

Definition 14 (Seed impression).

Definition 15 (Types of vertices).

Definition 16 (Requester pair classification).

Definition 17 (Pseudo-adjacency).

3.1.2 Signatures and Dynamic Programming States

Definition 18 (Partial Solution).

States of the Dynamic Programming Algorithms

Definition 19 (Signature).

3.2 Conditional Lower Bound

Proposition 20 (Theorem 3.9 in [3]).

Construction of 𝑮′.

Construction of 𝑯′.

4 NP-hardness When Maximum Degree is Bounded

Construction of 𝑯.

Construction of 𝑮.

Variable Gadgets.

5 Parameterized by Solution Size Plus Degeneracy

5.1 Conditional Lower Bound

Proposition 21.

Proof.

5.2 Algorithmic Result

6 Brute-force Algorithm and its Optimality

Proposition 22 (Lemma 4.1 in [28]).

Lemma 23.

Proof.

References

Construction of $G^{\prime}$ .

Construction of $H^{\prime}$ .

Construction of $𝑯$ .

Construction of $𝑮$ .