Bridging Treewidth and Clique-Width via Cograph-Modular-Treewidth

Our motivation is to bridge the algorithmic tractability gap between treewidth and clique-width. The same question was asked by Sæther and Telle [30] who introduced the graph parameter sm-width, which lies between treewidth and clique-width. Notably, some graph classes with unbounded treewidth, like distance-hereditary graphs, have bounded sm-width. In [30] the authors showed that MaxCut, Chromatic Number, Hamiltonian Cycle, and Edge Dominating Set are FPT when parameterized by sm-width.

Another parameter between treewidth and clique-width is called modular-treewidth and was introduced by Bodlaender and Jansen [4]. Notably Lampis [25] studied Chromatic Number parameterized by modular-treewidth ($\mathrm{𝚖𝚝𝚠}$), showing an algorithm that decides $k$-coloring in ${𝒪}^{\ast }({\left(\genfrac{}{}{0pt}{}{k}{\lfloor k/2\rfloor }\right)}^{\mathrm{𝚖𝚝𝚠}})$ time; this is FPT when parameterized by $k+\mathrm{𝚖𝚝𝚠}$. Hegerfeld and Kratsch [23] recently studied connectivity problems on modular-width. Notably, they define twinclass-treewidth which is equivalent to ours $𝒞$-modular treewidth when $𝒞$ is set to be $(\text{clique}\cup \text{edgeless})$, i.e., the class of all cliques and edgeless graphs. Several papers [25, 27, 29] use the name modular-treewidth to refer twinclass-treewidth.

Many natural problems are polynomial-time solvable on cographs, FPT when parameterized by treewidth, yet become intractable (e.g., W$[1]$-hard) under clique-width. Examples include Max Cut, Chromatic Number, Edge Dominating Set, Hamiltonian Cycle. Although Isomorphism is FPT when parameterized by treewidth [26], for clique-width it is only known to be in XP [22] and whether it is FPT or W$[1]$-hard remains open.

W[1]-hardness reductions for many of these problems exhibit unbounded treewidth due to a simple obstruction, e.g. big cliques or bi-cliques, which additionally form modules in the constructed graph. This, together with their tractability on treewidth, raises the question of whether simple modules can be exploited to design FPT algorithms.

In the following sections, we formally define $𝒞$-modular-treewidth, analyze its structural and algorithmic properties, and show its applicability to the above problems. Our results contribute to the broader goal of identifying and utilizing structural graph parameters that support efficient algorithms, lying between the extremes of treewidth and clique-width.

In Section 2.1 we clarify relations to other parameters and why results for modular-treewidth extend to our parameters. In particular, note that for Chromatic Number the number of colors is naturally bounded for graphs of treewidth, which is also true for independent-modular-treewidth. On the other hand, the number of colors is unbounded in cographs, and we support untractibility in this case by showing coloring is W$[1]$-hard by cograph-modular-treewidth.

To simplify the notation in this paper, we employ the following convention while discussing problems. We use the following shorthand for width parameters: $\mathrm{𝚝𝚠}$ for treewidth, $\mathrm{𝚌𝚠}$ for clique-width, $\mathrm{𝚒𝚖𝚝𝚠}$ for independent-modular-treewidth (i.e., $𝒞$-modular-treewidth with $𝒞$ as edgeless graphs), and $\mathrm{𝚌𝚖𝚝𝚠}$ for cograph-modular-treewidth (i.e., $𝒞$-modular-treewidth with $𝒞$ as cographs). For a graph problem $\mathrm{\Pi }$ and a width parameter $\mu \in \{\mathrm{𝚝𝚠},\mathrm{𝚌𝚠},\mathrm{𝚒𝚖𝚝𝚠},\mathrm{𝚌𝚖𝚝𝚠}\}$, when we represent it as $\mathrm{\Pi }/\mu$ it indicates that the problem $\mathrm{\Pi }$ is considered with parameter $\mu$. For example, Isomorphism$/\mathrm{𝚝𝚠}$ indicates Isomorphism parameterized by treewidth.

A tree decomposition of an undirected graph $G$ is a pair $(T,{\{X_t\}}_{t\in V(T)})$ where $T$ is a tree and $X_t\subseteq V(G)$ such that (i) for all edges $uv\in E(G)$ there exists a node $t\in V(T)$ such that $\{u,v\}\subseteq X_t$ and (ii) for all $v\in V(G)$ the subgraph induced by $\{t\in V(T)\mid v\in X_t\}$ is a non-empty tree. The width of a tree decomposition is ${\max }_{t\in V(T)}|X_t|-1$. The treewidth of $G$ is the minimum width of a tree decomposition of $G$.

Observe that Definition 2 is equivalent to partitioning $G$ into modules with each part inducing a graph from $𝒞$.

In other words, by the above definition we can construct $G$ by taking a graph $H$ of bounded treewidth and replace every vertex $u\in V(H)$ with a graph $p^{-1}(u)\in 𝒞$, making all the replacement vertices adjacent to the prior neighbors of $u$, see Figure 1. Observe that for each $v\in V(H)$ every $p^{-1}(v)$ forms a module of $G$. We call $H$ the module graph and the function $p$ the replacement function.

Note that if $𝒞$ contains a single-vertex graph then every graph has a $𝒞$-modular tree-decomposition as we can set $H=G$, $p$ to be identity and $𝒯$ to be the tree-decomposition of $G$.

We now show basic properties of this general definition.

With the class $𝒮$ being this restricted the replacement function $p$ cannot change the graph at all, hence, $G\approx H$ and we conclude that $G$ has treewidth $k$ if and only if it has $𝒮$-modular-treewidth $k$. $◀$

As $G$ is from the class $𝒞$ it follows that it can be created from a single vertex $u$ by replacing $u$ with $G$. The graph with a single vertex has treewidth $0$. $◀$

Consider a $𝒞$-modular tree-decomposition $(H,p,𝒯)$, then $(H,p,𝒯)$ is also a $𝒟$-modular tree-decomposition because any part of $p$ induces a graph of $𝒞$ which is a subset of $𝒟$; the other conditions remain unchanged and still hold. $◀$

It is clear that the usefulness of $𝒞$-modular-treewidth depends heavily on the chosen graph class $𝒞$. One challenge with general graph classes is to be able to find a $𝒞$-modular tree-decomposition; one central class in our work is the class of cograph and to overcome this challenge we exploit the nice structure implied by the presence of twins in the class of cographs.

As one can replace join with a sequence of 3 operations: complement, disjoint union, complement; it is not difficult to see that replacing (3) with taking complement of a cograph yields an equivalent (original) definition.

It was observed in [9] that each cograph has a unique representation by a cotree. We later use the fact that there is an algorithm to retrieve cotree and that tree isomorphism is a solved problem.

For a graph $G$, we denote its treewidth $\mathrm{𝚝𝚠}(G)$, clique-width $\mathrm{𝚌𝚠}(G)$, cograph-modular-treewidth $\mathrm{𝚌𝚖𝚝𝚠}(G)$, and independent-modular-treewidth $\mathrm{𝚒𝚖𝚝𝚠}(G)$.

We refer to [15] for an introduction to the area. A parameterized problem $(x,k)$ where $x$ is a string over $\mathrm{\Sigma }$ and a parameter $k\in \mathbb{N}$ is fixed-parameter tractable (or FPT) if it can be solved in $f(k)\cdot {|x|}^{𝒪(1)}$ time for some computable function $f$. The standard notion of fixed-parameter intractability is W[1]-hardness.

Towards a contradiction for (1), choose an $H$ that contains the minimum number of false twins and suppose that this number is positive. Let $u,v\in V(H)$ be one such pair of false twins. The function $p$ replaces each vertex of $H$ with a graph from $𝒞$ to obtain $G$. As $u,v$ are false twins in $H$ it follows that $\{u,v\}$ is a module in $H$. Let us alter the decomposition by removing $v$ to create $H^{\prime }$ and observe that $G$ can still be created from $H^{\prime }$ by creating $p^{\prime }=p$ except for setting ${(p^{\prime })}^{-1}(u)$ to be $G[p^{-1}(u)\cup p^{-1}(v)]$. This subgraph is in $𝒞$ because both $p^{-1}(u)$ and $p^{-1}(v)$ are in $𝒞$ and in $G$ there is no edge between them as $uv\notin E(H)$, and because $𝒞$ is closed under disjoint union. We removed $v$ so the new decomposition $(H^{\prime },p^{\prime },𝒯-v)$ contains fewer twins, a contradiction.

We prove (2) by a similar contradiction; assuming $𝒞$ is closed under joins and that $u,v$ are true twins in $H$, we show that $v$ can be removed because $G[p^{-1}(u)\cup p^{-1}(v)]$ is by $uv\in E(H)$ a join of the two graphs from $𝒞$. $◀$

We aim to find maximal modules that induce independent sets in the graph. $ℐ$ is closed under disjoint union so we invoke Lemma 17 and conclude that $G$ has an $ℐ$-modular tree-decomposition $(H,p,𝒯)$ where its module graph $H$ contains no false twins. To find such $H$ and $p$ of such a decomposition we first retrieve the false twin relation by comparing open neighborhoods of all pairs of vertices; this implies a partition $𝒫$ of $V(G)$.

From each part $P\in 𝒫$ we pick an arbitrary single representative $u^P\in P$. Let the modular graph $H$ be the graph induced on the representatives $H=G[\{u^P\mid P\in 𝒫\}]$. The above can be easily done in $n^{𝒪(1)}$ time. For every $v\in V(G)$ let $p(v)=u^P$ where $P\in 𝒫$ such that $v\in P$. As $𝒫$ splits the graph into parts of equivalent neighborhoods, we have that the parts are modules of $G$. For any pair of vertices $v_1,v_2\in V(G)$ we have $v_1{\sim }_G{v}_2\iff p(v_1){\sim }_{H}p(v_2)$ by $N(p(v_1))=N(v_1)$, $N(p(v_2))=N(v_2)$, and $H$ being an induced subgraph of $G$. $◀$

To retrieve a cograph-modular tree-decomposition we use a very similar argument as for the independent-modular tree-decomposition; a number of notions needs to be introduced first.

Let us establish notations regarding partitions. Let each partition be represented as a family of sets that correspond to the parts, i.e, for a set $\{a,b,c,d,e,f\}$ we can have its partition $\{\{a,b,c\},\{d,e\},\{f\}\}$. The procedure described below creates nested partitions (partitions of partitions), resulting in e.g. $\{\{\{a,b,c\}\},\{\{d,e\},\{f\}\}\}$. Let partition tree $T(U)$ of a set $U$ be a tree that corresponds to the bracket structure with labels of $U$ replaced with $\mathrm{\varnothing }$ – defined inductively, if $U$ is a label let $T(U)$ be a rooted tree with only the root vertex, otherwise $U=\{u_1,\mathrm{\dots },u_c\}$ and $T(U)$ is a rooted tree where the root has $c$ children – roots of its subtrees $T(u_1),\mathrm{\dots },T(u_c)$.

Let $G$ be a graph with cograph-modular-treewidth $k$. Let ${𝒫}_c(G)$ be a partition of $V(G)$ such that $u,v$ belong to the same part if and only if $N[u]=N[v]$. Let ${𝒬}_c(G)$ be the quotient graph over ${𝒫}_c(G)$, i.e., graph ${𝒬}_c(G)=({𝒫}_c(G),\{\{P,Q\}\mid P,Q\in {𝒫}_c(G),P\ne Q,u\in P,v\in Q,uv\in E(G)\})$. Similarly for open neighborhoods, let ${𝒫}_o(G)$ be a partition where $u,v\in P\in {𝒫}_o(G)$ if and only if $N(u)=N(v)$ and let ${𝒬}_o(G)$ be the quotient graph over ${𝒫}_o(G)$. Note that taking the quotient graph results in a graph that is isomorphic to a graph where all but one vertex is removed from each part because the considered parts are always modules of the graph.

As $G^{\prime }$ is a cograph it contains a pair of vertices that in $G[V(G^{\prime })]$ are true or false twins [9, Theorem 2]. Suppose $G^{\prime }$ contains $u,v\in V(G^{\prime })$ that are true twins in $G[V(G^{\prime })]$, so $N[u]\cap V(G^{\prime })=N[v]\cap V(G^{\prime })$. As $u,v$ are part of the module their neighborhood in $V(G)\setminus V(G^{\prime })$ is identical. We conclude that $u,v$ are true twins in $G$ as well. If $G^{\prime }$ contains false twins instead, the proof is identical. $◀$

Now, we use the above lemma to find a tree decomposition of the module graph by first identifying twins of $G$, alternating between identifying true or false twins, and then invoking the algorithm to find the tree decomposition of the resulting graph.

We define a sequence of graphs $G_0,G_1,\mathrm{\dots },G_{2q}$ where $G_0=G$ and for each $i\in [q]$ the graph $G_{2i-1}={𝒬}_c(G_{2i-2})$ and $G_{2i}={𝒬}_o(G_{2i-1})$; let $q$ be the minimum such that $G_{2q}={𝒬}_c({𝒬}_o(G_{2q+2}))$. Note that $q\le n$ as by the definition for each $i\in [q]$ the graphs $G_{2i}$ and $G_{2i-2}$ are distinct; by the construction we have . I.e., in the above we constructed a sequence of quotient graphs over alternating partitions ${𝒫}_c$ and ${𝒫}_o$ which ends at a point where the application does not change the graph, i.e., all vertices have distinct open neighborhoods and distinct closed neighborhoods. All of this takes at most $n^{𝒪(1)}$ time as $q\le n$, and each step takes at most polynomial-time.

Note that due to Lemma 17 graph $H$ should not contain twins; the above process gets rid of them. Moreover, due to Lemma 19, if there is a module that induces a cograph then the process eventually reduces it to a single vertex. We set $H=G_{2q}$ which is a module graph of $G$ and $p$ can be constructed according to Lemma 17 in a straight-forward manner. $◀$

To finish, we apply the algorithm of Korhonen [24] which either returns a tree-decomposition $𝒯$ of $H$ of width $2k+1$ or concludes that the treewidth of $H$ is more than $k$ in $2^{𝒪(k)}\cdot |V(H)|$ time. We return $(H,p,𝒯)$ as the independent-modular tree-decomposition.

Note that in the proof of Theorem 20 the labels assigned to vertices correspond to cotrees of the particular modules. This could be utilized to retrieve cotrees immediately, but for simplicity we will retrieve the cotrees of $p^{-1}(u)$ for each $u\in V(H)$ independently using [6].

The procedure assigns $\gamma$ to every root of every subtree (i.e., every vertex of every tree) so that two subtrees are isomorphic if and only if their $\gamma$ are equal. We can assume that the roots of all the trees in the set are children of a new dummy root so we can focus on processing a single tree. In essence, the vertices of the rooted tree are labelled bottom-up as follows. Each leaf gets label 0 and each inner vertex gets a label determined from the sorted labels of its children. More precisely, if label combination was never seen before it assigns the lowest unused $\mathbb{N}$; hence, the maximum integer used for a label is no more than the total number of vertices. It follows that isomorphic subtrees get the same label, and that the used labels are upper bound by the number of processed vertices. To compare two different trees one needs to preserve the label assigning function from one tree and use it to label the other tree – two trees are deemed isomorphic if they end up having the same-labelled root. $◀$

We will use Lemma 23 to get integers for cotrees of cographs that make up modules of our graph. These numbers will be used as labels and we solve the labeled instance using transformation from the following lemma.

Let us create $\widehat{G}$ from $G$ by first subdiving all edges once and then to every vertex $u\in V(G)$ attaching $\delta (u)+2$ new leaves. We create ${\widehat{G}}^{\prime }$ from $G^{\prime }$ in the same way. This transformation runs in $n^{𝒪(1)}$ time. Due to the subdivision the transformation creates a bipartite graph. All of the new leaves are in one part of the bipartition. On the other hand, the old leaves (those in $G$) are not leaves in $\widehat{G}$ as to each of them we attached at least 2 new leaves. Note that the transformation is label agnostic and so if $G{\approx }_{\delta }{G}^{\prime }$ then $\widehat{G}\approx {\widehat{G}}^{\prime }$. In the other direction, assuming $\widehat{G}\approx {\widehat{G}}^{\prime }$ we know that the parts with the leaves need to be mapped to each other. The number of adjacent leaves of a vertex is invariant under isomorphism and structure of the graph is clearly reflected in subdivision vertices, so it is straight-forward to lift the isomorphism to $G{\approx }_{\delta }{G}^{\prime }$. $◀$

By Corollary 22 we either get cograph-modular tree-decomposition $(H,p,𝒯)$ of $G$ and $(H^{\prime },p^{\prime },{𝒯}^{\prime })$ of $G^{\prime }$, each of width at most $2k+1$, or conclude that one of the graphs has cograph-modular-treewidth more than $k$. Then, for each vertex $u\in V(H)$ we take the induced subgraph $G[p^{-1}(u)]$ and retrieve its cotree $C_u$; similarly we retrieve cotrees of all the vertices in $G^{\prime }$. Now we create a labeling $\gamma :V(G)\cup V(G^{\prime })\to \mathbb{N}$. Then, for every subgraph $\{G[p^{-1}(u)]\mid u\in V(H)\}$ we retrieve its cotree $C_u$ [6]; similarly for $H^{\prime }$ we get cotrees $C_v^{\prime }$. Now we run Lemma 23 for the set of all retrieved cotrees $\{C_u\mid u\in (V(G)\cup V(G^{\prime }))\}$, let $\gamma (u)=\delta (C_u)$, i.e., we set $\gamma (u)$ to be the label that uniquely identifies the cotree $C_u$ and subsequently also uniquely identifies the respective cograph. Note that $\gamma$ has no values bigger than $|V(G)|+|V(G^{\prime })|$. Next, we invoke Lemma 24 to transform $H,H^{\prime }$ to $\widehat{H},{\widehat{H}}^{\prime }$. Last, we use [26] to determine whether $\widehat{H}$ is isomorphic to ${\widehat{H}}^{\prime }$ in $2^{𝒪(k^5\log k)}\cdot {(|V(\widehat{H})|+|V({\widehat{H}}^{\prime })|)}^5$ time.

We claim that the answer to whether $G$ is isomorphic to $G^{\prime }$ is equivalent to answering whether $\widehat{H}$ is isomorphic to ${\widehat{H}}^{\prime }$. Indeed, observe that Corollary 22 obtains the cograph-modular tree-decomposition in a label-agnostic way so $G\approx G^{\prime }$ if and only if the bijection that witnesses $H\approx H^{\prime }$ maps to each other vertices that represent the same underlying cographs, i.e., a bijection $\alpha :H\to H^{\prime }$ must satisfy $p^{-1}(u)\approx p^{\prime -1}(\alpha (u))$ for every $u\in V(H)$. We modeled this requirement by using bijection between cographs and cotrees, then using Lemma 23 to get the auxiliary labeling $\gamma$, and requiring $\gamma$-preserving isomorphism. Last, we used a transformation Lemma 24 which produces an equivalent instance. $◀$

Our proof is based on a construction similar to that of [20], with specific modifications – namely, the addition of further gadget structures, which establishes the W[1]-hardness of the Chromatic Number when parameterized by clique-width. We give a reduction from Equitable Coloring/$\mathrm{𝚝𝚠}+r$ which is known to be W$[1]$-hard [18]. In the Equitable Coloring problem one is given a graph $G$ on $n$ vertices and integer $r$ and asked whether $G$ can be properly $r$-colored in such a way that the number of vertices in any two color classes differs by at most 1 (such coloring is called an equitable $r$-coloring). Notice that if $n$ is divisible by $r$ this implies that all color classes must contain the same number of vertices. In our reduction, we will assume that in the instance we reduce from, $n$ is divisible by $r$. For a justification of this assumption, if $r$ does not divide $n$ we can add a clique of size $r-(n-\lfloor n/r\rfloor r)$ to $G$. We reduce from the exact version of Equitable Coloring, that is, the version where we are looking for an equitable coloring of $G$ with exactly $r$ colors.

Given an input $(G,r)$ to Equitable Coloring, we construct an instance $(H,r^{\prime })$ of Chromatic Number as follows (see Figure 3). Let $n=|V(G)|$ and $r^{\prime }=r+nr$. We start with a copy $G^{\prime }$ of $G$. We add a clique $Q$ of size $nr$ and connect every vertex of $Q$ to every vertex of $G^{\prime }$ by an edge. We add a clique $P$ of size $r^{\prime }$ to $H$, called palette. The set $P$ is partitioned into $r+1$ parts: $P=P^M\stackrel{\Gamma }{\cdot }\cup P_1\stackrel{\Gamma }{\cdot }\cup P_2\stackrel{\Gamma }{\cdot }\cup \mathrm{\dots }\stackrel{\Gamma }{\cdot }\cup P_r$, where $|P^M|=r$, $|P_i|=n$ (for $i\in [r]$). The vertices of $P^M$ are denoted by $p_1,p_2,\mathrm{\dots },p_r$. For each vertex $v\in P_M$ and each vertex $w\in Q$, we add the edge $vw$. For each $i\in [r]$, we add a set $S_i$ of $n$ vertices which contains copies of all vertices of $G$. For each vertex $u\in V(G)$ and each $i\in [r]$, we assign vertices $u_{P_i}\in P_i$ and $u_{S_i}\in S_i$. For each vertex $u\in V(G)$ and each $i\in [r]$, we add the edge $u{u}_{P_i}$. For every vertex $u\in V(G)$ and each $i\in [r]$, we make $u_{S_i}$ adjacent to $u$ and the entire palette $P$ except for $u_{P_i}$ and $p_i$. For each $i\in [r]$, we add a clique $C_i$ of $\frac{n(r-1)}{r}$ vertices and make every vertex of $C_i$ adjacent to all the vertices of $S_i$ and the entire palette $P$ except for $P_i$. Now we show the correctness of the reduction.

Claims 27, 28 and 29 together give a parameterized reduction from Equitable Coloring for $\mathrm{𝚝𝚠}+r$ into Chromatic Number/$\mathrm{𝚌𝚖𝚝𝚠}$. Moreover, as per our construction, this hardness holds even when every cograph in the underlying decomposition is a clique or an independent set. This completes the proof of Theorem 26. $◀$

In the proof of W[1]-hardness of Hamiltonian Cycle/$\mathrm{𝚌𝚠}$ by Fomin et al. [20], the constructed gadget contains large independent modules. These modules have the property that, if each were contracted into a single vertex, the resulting graph would have bounded treewidth. We exhibit this property towards proving Theorem 36. For the sake of completeness, we present the same construction below, omitting the proof of the reduction (as it remains identical), but we include a proof demonstrating that the underlying graph has bounded treewidth.

We give a reduction from Capacitated Dominating Set$/\mathrm{𝚝𝚠}$ which is known to be W$[1]$-hard [20]. We start with descriptions of auxiliary gadgets.

The first auxiliary gadget is the graph $L_1$ with the vertex set $\{x,y,z,a,b,c,d\}$ and the edge set $\{xa,ab,bc,cd,dy,bz,cz\}$. Let $P_1$ be the path $xabzcdy$ and $P_2=xabcdy$.

The second auxiliary gadget is the graph $L_2$ with the vertex set $\{x,y,z,s,t,a,b,c,d,e,f,g,h\}$. Initially, the edges $\{xa,ab,bz,cz,cd,dy,se,ef,fb,ch,hg,gt\}$ in are added to its edge set. Then an $x$-$y$ path $x{w}_1\mathrm{\cdots }{w}_{9}y$ of length 10 is added, and edges $f{w}_3$, $w_1{w}_6$, $w_4{w}_9$, $w_{7}h$ are included in the set of edges. Let $P=xabzcdy$, $R_1=sefbax{w}_1{w}_2\mathrm{\dots }{w}_{9}ydchgt$, and $R_2=sef{w}_3{w}_2{w}_1{w}_6{w}_5{w}_4{w}_9{w}_8{w}_{7}hgt$.

Let $(G,c)$ be a capacitated graph with the vertex set $\{v_1,\mathrm{\dots },v_n\}$ and $m$ edges, and let $k$ be a positive integer. The construction of $H$ is as follows:

• $\mathrm{■}$

  For every vertex $v_i$, four vertices $a_i$, $b_i$, $c_i$, and $w_i$ are introduced, and the vertices $b_i$ and $c_i$ are joined by $c(v_i)+1$ paths of length two. Let $C_i$ denote the set of middle vertices of these paths, and $X_i=C_i\cup \{a_i,b_i,c_i\}$. Then a copy $L_i^2$ of the graph $L_2$ with $z=w_i$ is added, and vertices $x$ and $y$ of this gadget are joined by edges to $a_i$ and $b_i$, respectively. By $s_i$ and $t_i$ we denote the vertices $s$ and $t$, respectively, of $L_i^2$. The paths corresponding to $P$ in $L_i^2$ is called $P^i$.

• $\mathrm{■}$

  For every edge $v_i{v}_j\in E(G)$ with , a copy $L_{ij}^2$ of $L_2$ is attached with $z=w_j$ and vertices $x$ and $y$ made adjacent to all the vertices of $C_i$. The vertices corresponding to $s$ and $t$ are called $s_{ij}$ and $t_{ij}$, respectively, in $L_{ij}^2$. Furthermore, let $x_{ij}$ and $y_{ij}$ denote the vertices corresponding to $x$ and $y$, respectively, in $L_{ij}^2$. The paths corresponding to $P$, $R_1$, and $R_2$ are called $P^{ij}$, $R_1^{ij}$, and $R_2^{ij}$, respectively, in $L_{ij}^2$.

• $\mathrm{■}$

  Next we add two vertices $g$ and $h$ which are joined by ${\sum }_{i=1}^n(c(v_i)+4)+n+2m+1$ paths of length two. Let $Y$ be the set of middle vertices of these paths. All vertices $s_i$, $t_i$, $s_{ij}$, and $t_{ij}$ are joined by edges with all vertices of $Y$. For every vertex $r\in X_i$, $i\in [n]$, a copy $L_r^1$ of $L_1$ with $z=r$ is attached and the vertices $x$ and $y$ of this gadget are joined to all vertices of $Y$. We let $x_r$ and $y_r$ denote the vertices corresponding to $x$ and $y$, respectively, in $L_r^1$. Similarly, $P_1^r$ and $P_2^r$ denote paths in $L_r^1$ corresponding to $P_1$ and $P_2$, respectively.

• $\mathrm{■}$

  Finally, we add $k+1$ vertices, namely $\{p_1,\mathrm{\dots },p_{k+1}\}$, and make them adjacent to all the vertices $\{a_i,c_i\mid 1\le i\le n\}$ and to $g$ and $h$.

Claims 37 and 38 together give a parameterized reduction from Capacitated Dominating Set/$\mathrm{𝚝𝚠}$ to Edge Dominating Set/$\mathrm{𝚒𝚖𝚝𝚠}$. This completes the proof of Theorem 36. $◀$