Parameterized Edge Hamiltonicity

Abstract

We study the parameterized complexity of the classical Edge Hamiltonian Path problem and give several fixed-parameter tractability results. First, we settle an open question of Demaine et al. by showing that Edge Hamiltonian Path is FPT parameterized by vertex cover, and that it also admits a cubic kernel. We then show fixed-parameter tractability even for a generalization of the problem to arbitrary hypergraphs, parameterized by the size of a (supplied) hitting set. We also consider the problem parameterized by treewidth or clique-width. Surprisingly, we show that the problem is FPT for both of these standard parameters, in contrast to its vertex version, which is W[1]-hard for clique-width. Our technique, which may be of independent interest, relies on a structural characterization of clique-width in terms of treewidth and complete bipartite subgraphs due to Gurski and Wanke.

Valia Mitsou: This work was done while the author was at the Graduate Center, CUNY and visiting Kyoto University. Research is (partly) supported by JST ERATO Minato project.

Yushi Uno: Research partially supported by KAKENHI Grand numbers 23500022 and 25106508.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The focus of this paper is the Edge Hamiltonian Path problem, which can be defined as follows: given an undirected graph $G(V,E)$, does there exist a permutation of $E$ such that every two consecutive edges in the permutation share an endpoint? This is a very well-known graph-theoretic problem, which corresponds to the restriction of (vertex) Hamiltonian Path to line graphs. Despite some superficial similarity to the problem of finding an Eulerian path, this problem has long been known to be NP-complete, even for graphs which are bipartite or have maximum degree 3 [1, 25, 29].

The Edge Hamiltonian Path problem is a very natural graph-theoretic problem with a long history (see e.g. [4–8, 24]). In this paper, we investigate the complexity of this problem from the parameterized complexity perspective. More specifically, we consider the case where some structural parameter of the input graph $G$, such as its treewidth, has a moderate value. Despite the problem’s prominence, to the best of our knowledge, Edge Hamiltonian Path has never before been studied in this setting. Such an investigation is of inherent interest from the point of view of graph theory and parameterized complexity. Beyond this, we are partially motivated by a specific question recently asked explicitly by Demaine et al. [14]. In their investigation of the card game UNO, the authors of [14] present an XP (i.e. running in $n^{f(k)}$) dynamic programming algorithm for Edge Hamiltonian Path on bipartite graphs, where $k$ is the size of the smaller part. They then, quite naturally, ask if this can be improved to an FPT algorithm. In this paper, we present a number of results that positively settle not only this, but several other more general such questions (the question from [14] was also independently settled by Dey et al. [15]).

Overview of results. We give fixed-parameter tractability results for Edge Hamiltonian Path and its variant Edge Hamiltonian Cycle, which we show to be essentially equivalent. Our first task is to consider the problem parameterized by the size of the vertex cover of the input graph. We establish that, not only is the problem FPT, but it also admits a cubic kernel through an algorithm that locates and deletes irrelevant edges. This result settles the question from [14] as for a bipartite graph, one part being small implies a small vertex cover. We then go on to give a much more general direct FPT algorithm for the problem, which can still be applied even if we consider the problem on arbitrary hypergraphs with the parameter being the size of a hitting set which is supplied with the input. As a corollary, we note that this result implies that (vertex) Hamiltonian Path is FPT when parameterized by the chromatic number of the complement of the input graph.

Our next direction is to consider the problem on graphs parameterized by treewidth and clique-width. The complexity of Edge Hamiltonian Path for these parameters was previously unknown, since this is also a more general question than the one posed in [14]. Our first observation is that fixed-parameter tractability for Edge Hamiltonian Cycle parameterized by treewidth can be obtained from standard meta-theorems, if one relies on an alternative characterization of the problem first given by Harary and Nash-Williams almost 50 years ago [22]. This alternative characterization allows one to recast the ordering problem as the problem of finding a connected Eulerian subgraph whose vertices form a vertex cover of the original graph. The alternative problem with a little work, can be expressed in a variant of Monadic Second Order logic. For the sake of completeness, we also sketch a direct treewidth-based dynamic programming algorithm using this formulation.

Having settled the problem for treewidth, the natural next step is to consider Edge Hamiltonian Cycle parameterized by clique-width, a prominent structural graph parameter that generalizes treewidth. It is important to note here that the (more common) vertex version of the problem exhibits a sharp complexity jump between these two parameters: Hamiltonian Cycle is FPT for treewidth but for clique-width the problem is W[1]-hard and therefore does not admit an FPT algorithm under standard complexity assumptions [19]. In what is perhaps the most surprising result of this paper, we show that Edge Hamiltonian Cycle remains FPT even for clique-width, despite this parameter’s additional generality. On a high level, our strategy is to rely on a characterization of bounded clique-width graphs given by Gurski and Wanke [20] which states roughly that if a graph has small clique-width and no large complete bipartite subgraphs, then it has small treewidth. We devise an algorithm that locates and “reduces” large complete bipartite subgraphs in the input graph, without affecting the answer or increasing the clique-width. By repeatedly applying this step, we end up with a graph of small treewidth for which the problem is FPT. This idea, which was also used in [28], is a rare algorithmic application of the characterization of [20], and may be of independent interest.

2 Preliminaries

We assume that the reader is familiar with the basics of parameterized complexity. In particular, we use the definitions of the classes FPT, XP as well as the notion of a kernelization algorithm and of polynomial kernels (see [16, 18, 26]).

We will use the definition of treewidth, and in particular the notion of “nice” tree decompositions (see the survey [3]). We also use the notion of clique-width (see [13, 17, 23]). Let us briefly review the definition. The class of graphs of clique-width $k$ contains all single-vertex graphs where the only vertex has a label from $\{1,\ldots ,k\}$. Furthermore, the class is closed under the following operations: disjoint union of two graphs; renaming of all vertices with some label $i$ to some label $j$; and joining by new edges of all vertices with some label $i$ to all vertices with some label $j$. All graph classes with bounded treewidth also have bounded clique-width, but the reverse is not true [10].

We will also rely on the following theorem of Gurski and Wanke which intuitively states that large complete bipartite graphs are what separates treewidth from clique-width:

Theorem 1

[20]. Let $G$ be a graph of clique-width $k$. If $G$ does not contain the complete bipartite graph $K_{t,t}$ as a subgraph, then $tw(G) \le 3kt$.

We will consider the Edge Hamiltonian Path and Edge Hamiltonian Cycle problems. As mentioned, in these problems we are looking for a permutation of the edges of the input graph so that any two consecutive edges share an endpoint (in the latter problem, also the first and last edge must share an endpoint). We call such a permutation an edge-Hamiltonian path (respectively an edge-Hamiltonian cycle). We will mostly view these as graph problems, but this problem definition applies equally well to hypergraphs, if we require that two consecutive hyperedges share a common vertex. Hypergraphs are the subject of Sect. 4. Recall that for a graph or hypergraph $G(V,E)$, its line graph is the graph $G'(E,H)$ where $(e_1,e_2)\in H$ if and only if $e_1,e_2$ share a vertex in $G$. The Edge Hamiltonian Path problem on $G$ is equivalent to the Hamiltonian Path problem on $G'$.

For the graph case, it will be useful to recast these ordering problems as subgraph problems. First, recall that a graph is Eulerian if it is connected and all its vertices have even degree. A Dominating Eulerian Subgraph of a graph $G(V,E)$ is a subgraph $G'(V',E')$ of $G$ such that all edges of $E$ have an endpoint in $V'$, that is, $V'$ is a vertex cover of $G$, and $G'$ is Eulerian. We will use the following classical observation of Harary and Nash-Williams:

Theorem 2

[22]. A graph has an edge-Hamiltonian cycle if and only if it contains a dominating Eulerian subgraph.

Finally, let us mention that we will deal with Edge Hamiltonian Path and Edge Hamiltonian Cycle interchangeably, depending on which problem makes the description of our algorithms easier. The reader can easily verify that all our arguments apply to both problems with very minor modifications. It is also not hard to show the following:

Lemma 1

For the following parameters and for sufficiently large graphs, Edge Hamiltonian Path is FPT if and only if Edge Hamiltonian Cycle is FPT: vertex cover, treewidth, clique-width and hypergraph hitting set.

Proof of Lemma 1 as well as all other missing proofs appears in the full version of the paper.

3 Vertex Cover

In this section we consider the Edge Hamiltonian Path problem parameterized by the size of the vertex cover $k$. We show that the problem has a cubic in $k$ kernel. As in the following sections, we assume that together with the input graph $G(V,E)$ we are given a vertex cover $S$ of $G$ with $|S|=k$. Note though, that this assumption is not important, since a 2-approximate vertex cover can be found in polynomial time [9].

Below follow some definitions which will make the presentation of the results smoother. We assume that the vertices of $G$ are labeled in some lexicographically ordered fashion, and in particular that $S=\{u_1,\ldots ,u_k\}$.

Definition 1

An edge $e\in E$ is defined to be of type $i$ if it is incident to $u_i\in S$ but not incident to any other $u_j\in S$ for $j<i$.

Definition 2

Let $P$ be an edge-Hamiltonian path of $G$. For $i\in \{1,\ldots ,k\}$, a group of type $i$ is a maximal set of edges of type $i$ which are consecutive in $P$. We say that an edge is special if it is the first or the last edge of a group.

The special edges essentially form the backbone of the edge-Hamiltonian path $P$. A piece of intuition that will become useful later is that, if one fixes these edges in a proper edge-path, the remaining edges will be easy to deal with, because they are allowed to move freely in and out of groups.

Our next goal then is to show that if a graph has an edge-Hamiltonian path $P$, then it has one where few edges are special. This is summarized in Lemma  2 and Corollary 1. Intuitively, the core idea is a flipping argument: if the same group types appear too many times in a solution, we can reverse a sub-path to obtain a solution with fewer groups.

Lemma 2

Let $G$ be an edge-Hamiltonian graph. Then, there exists an edge-Hamiltonian path $P$ of $G$ with the following property: for any $i,j\in \{1,\ldots ,k\}$, an edge of type $j$ appears directly after an edge of type $i$ at most once.

Proof

(sketch)

Suppose that $P'$ is an edge-Hamiltonian path of $G$ in which some group of type $i$ immediately precedes some group of type $i$. Then, we can create a valid path $P$ by reversing the middle part of this path and merging the two groups of type $i$ and those of type $j$.

The new path has strictly fewer groups. Repeating this process at most a linear (in $|E|$) number of times results in an edge-Hamiltonian path $P$ with the stated property.    $\square$

Corollary 1

Let $G$ be an edge-Hamiltonian graph. Then, there exists an edge-Hamiltonian path $P$ of $G$ such that for all $i\in \{1,\ldots ,k\}$, $P$ contains at most $k$ groups of type $i$. Therefore, $P$ contains at most $k^2$ groups in total, and for each $i\in \{1,\ldots ,k\}$ there exist at most $2k$ special edges of type $i$.

We have now proved that if a solution exists, it must have a certain nice form. Let us make one more easy observation.

Lemma 3

Let $G(V,E)$ be an edge-Hamiltonian graph. Then, there exists an edge-Hamiltonian path $P$ such that, for all $i\in \{1,\ldots ,k\}$ for which there exist at least $k+1$ edges of type $i$, $P$ has a group of type $i$ with size at least $2$.

Let us note that Lemma 2, Corollary 1 and Lemma 3 still hold even if $G$ is a hypergraph. We will make use of this in the next section.

We are now ready to state the main reduction rule and sketch its correctness.

Lemma 4

Let $G(V,E)$ be a graph, and $S=\{u_1,\ldots ,u_k\}$ a vertex cover of $G$ of size $k$. Suppose that there exists an edge $(u_i,w)$ satisfying the following:

• 1. $w\notin S$

• 2. There are at least $k+2$ edges of type $i$ in $G$

• 3. For all $u_j\in S$ such that $(u_j,w)\in E$ we have $|(N(u_i)\cap N(u_j))\setminus S|>4k$

Then $G(V,E)$ has an edge-Hamiltonian path if and only if $G'(V,E{\setminus }\{(u_i,w)\})$ does.

Proof

(sketch)

For the one direction, suppose that $G$ has an edge-Hamiltonian path $P$. We construct a path $P'$ where $(u_i,w)$ is removed. Let $e_1,e_2$ be the edges appearing immediately before and after $(u_i,w)$ in $P$. Suppose they do not share an endpoint (if they do, we can construct $P'$ by deleting $(u_i,w)$ from $P$). Since they both share an endpoint with $(u_i,w)$ we assume without loss of generality that $e_1$ is incident on $u_i$ and $e_2=(u_j,w)$. (Observe that here we have used the fact that $G$ is a graph, so the rest of our argument does not generalize to hypergraphs).

We know now by the last condition that $N(u_j)\cap N(u_i)$ contains at least $4k+1$ vertices of $V{\setminus } S$. By Corollary 1 and pigeonhole principle, there exists a vertex of $(N(u_i)\cap N(u_j)){\setminus } S$, call it $z$, such that $(u_i,z)$ and $(u_j,z)$ are not special.

Because $(u_i,z)$ is not special, the two edges appearing immediately before and after it are both incident on $u_i$. Therefore, deleting $(u_i,z)$ still leaves us with a valid edge-path. Similar reasoning can be used for $(u_j,z)$. We construct a path $P'$ as follows: delete $(u_i,w), (u_i,z)$ and $(u_j,z)$ from $P$ and then insert $(u_i,z),(u_j,z)$ between $e_1$ and $e_2$. This is a valid solution for $G'$.       $\square$

The proof of the other direction is easy and appears in the full version.

Lemma 4 now leads to the following theorem.

Theorem 3

Edge Hamiltonian Path has a kernel with $O(k^3)$ edges, where $k$ is the size of the input graph’s vertex cover.

4 Hypergraphs

In this section we present an FPT algorithm for Edge Hamiltonian Path on hypergraphs parameterized by the size of a (supplied) hitting set. As an interesting consequence, our algorithm also establishes fixed-parameter tractability for a novel parameterization of Hamiltonian Path, namely when the parameter is the chromatic number of the input graph’s complement.

In this section, $G(V,E)$ will be a hypergraph (that is, $E$ is a collection of arbitrary subsets of $V$). We assume that the input also contains a hitting set $S\subset V$ of size $k$, that is, a set of vertices that intersects all hyperedges. Unlike the previous section, this is not an inconsequential assumption, since finding even an approximate hitting set is generally a hard problem. However, observe that for hypergraphs of bounded rank (i.e. hyperedge size), a hitting set can be computed in FPT time and hence this requirement is nullified on such instances.

We will rely on the fact that much of the material of the previous section carries through unchanged. In particular, Definitions 1, 2, also apply to hypergraphs. Then, Lemma 2, Corollary 1, and Lemma 3 hold for the case of hypergraphs as well. Unfortunately, Lemma 4 does not seem to generalize naturally in this case.

Let us thus describe a different algorithm for this problem. As mentioned, one way to proceed is to try to identify the special hyperedges which form the backbone of a path. Once these have been found, the problem becomes much easier. We will use a color-coding scheme to assist us in selecting these special hyperedges. The high-level idea is the following: for every $i\in \{1,\ldots , k\}$ such that there are at least $2k$ hyperedges of type $i$, color these hyperedges with $2k$ colors uniformly at random. Then, merge (that is, take the union) of all hyperedges of type $i$ that took the same color to a single hyperedge. This process results in a hypergraph $G'$ with $O(k^2)$ hyperedges. We want to show that if this hypergraph has an edge-Hamiltonian path then $G$ does as well, while if $G$ has an edge-Hamiltonian path then $G'$ has one with non-negligible probability. The “good colorings” that give us this non-negligible probability are those that assign a different color to each special edge.

We are now ready to state the main result of this section.

Theorem 4

Given a hypergraph $G(V,E)$ and a hitting set $S=\{u_1,\ldots ,u_k\}$ of $G$, there is an FPT algorithm that decides if $G$ has an Edge Hamiltonian Path in time $2^{O(k^2)}n^{O(1)}$.

An interesting consequence of Theorem 4 is that it implies fixed-parameter tractability for a non-standard parameterization of Hamiltonian Path. The parameterization we are considering is by the complement chromatic number, that is, the chromatic number of the input graph’s complement. We are naturally led to this observation, because the line graph of a hypergraph with a hitting set of size $k$ has a vertex set that can be partitioned into at most $k$ cliques. To the best of our knowledge, this parameterization of Hamiltonian Path has not been considered before.

Corollary 2

Given a graph $G(V,E)$ and a proper $k$-coloring of its complement graph, there exists an FPT algorithm that decides if $G$ has a Hamiltonian Path in time $2^{O(k^2)}n^{O(1)}$.

5 Treewidth and Clique-Width

In this section we consider the Edge Hamiltonian Cycle problem parameterized by treewidth or clique-width. As is customary for these parameters, we will assume that a decomposition of width $k$ (or a clique-width expression with $k$ labels) is given to us with the input. This assumption is not necessary though, as both parameters can be approximated in FPT time (see [2, 27]).

Let us first consider treewidth. One obvious approach we could try to follow is to use the fact that if $G$ has treewidth $k$, its line graph has clique-width $O(k)$ [21]. Since deciding Edge Hamiltonian Cycle on $G$ is equivalent to deciding Hamiltonian Cycle on its line graph, this would give an XP algorithm using known results for the latter problem (this is similar to the approach of [14]). Unfortunately, since Hamiltonian Cycle is W[1]-hard for clique-width, this approach could not lead to an FPT algorithm for Edge Hamiltonian Cycle on treewidth. We thus have to recast the problem.

We will rely on Theorem 2, which states that the existence of an edge-Hamiltonian cycle is equivalent to the existence of a dominating Eulerian subgraph. Thus, we can view Edge Hamiltonian Cycle as a subgraph problem rather than an ordering problem. This formulation allows us to express the problem in a variant of MSO logic, without reference to orderings. We can then invoke standard meta-theorems to obtain fixed-parameter tractability for treewidth.

Let us sketch the basic idea. Recall that MSO$_2$ logic allows one to express properties involving sets of vertices or edges (see [12]). Dominating Eulerian Subgraph is the problem of looking for a set of vertices $V'$ and a set of edges $E'$ such that: all edges of $E$ have an endpoint in $V'$; the graph $G'(V',E')$ is connected; all vertices of $G'(V',E')$ have even degree. The first two properties are well-known to be expressible in MSO logic. Interestingly, the third property is expressible in Counting MSO$_2$ (CMSO$_2$) logic, an extension of MSO$_2$ which is still FPT for treewidth [11, 23]. Thus, Edge Hamiltonian Cycle is expressible in CMSO$_2$ and is therefore FPT for treewidth.

We can use standard techniques to obtain the following:

Theorem 5

Given a graph $G$ and a tree decomposition of width $k$, there exists an algorithm deciding if $G$ has an edge-Hamiltonian cycle in time $k^{O(k)} n^{O(1)}$.

Let us now move to the main result of this section, which is the tractability of Edge Hamiltonian Cycle parameterized by clique-width. Our high-level strategy will be to eliminate complete bipartite subgraphs from the input graph, without increasing the graph’s clique-width and without affecting the answer of the problem. If we can repeat this process, we will in the end have a graph with small clique-width and no large complete bipartite subgraphs. By Theorem 1, the graph will have small treewidth and we can use Theorem 5.

Our main tool will be a reduction lemma (Lemma 6). Roughly speaking, the lemma states that if we find a sufficiently large complete bipartite graph in $G$ with bipartition $A,B$, we can reduce it as follows: first we remove all its edges and then we add three new vertices which are connected to all vertices of both $A$ and $B$. This transformation should not affect the answer.

To prove Lemma 6, it will be useful to first prove the following statement. Roughly speaking, it says that if a graph contains a $K_{3,3}$ (or larger) complete bipartite subgraph, then any Dominating Eulerian Subgraph can be edited to produce a solution using all its vertices.

Lemma 5

Let $G(V,E)$ be a graph and $A,B\subseteq V$, with $A,B$ disjoint sets, $|A|, |B|\ge 3$ and $A\times B\subseteq E$. If $G$ has a dominating Eulerian subgraph then it also has a dominating Eulerian subgraph $G_0(V_0,E_0)$ such that $(A\cup B)\subseteq V_0$ and $E_0\cap (A\times B)\ne \emptyset$.

Proof

Suppose that $G$ has a dominating Eulerian subgraph $G_0(V_0,E_0)$. We will edit this solution by adding vertices and adding or removing edges until the stated properties are achieved. In the remainder, when we say that we flip an edge $e$ we mean that, if $e\in E_0$ then we remove it from $E_0$, otherwise we add it to $E_0$ and add its endpoints to $V_0$.

Let us first establish that $|(A\cup B) {\setminus } V_0|\le 1$ as follows: if $V_0$ does not fully contain one of the two sets $A,B$, it must fully contain the other (because $V_0$ is a vertex cover). Suppose without loss of generality that $B\subseteq V_0$. If there exist $v_1,v_2\in A{\setminus } V_0$, then pick two vertices $u_1,u_2\in B$. We can flip all the edges of $\{u_1,u_2\}\times \{v_1,v_2\}$ and produce a valid solution with more vertices.

Now, if there is a single vertex $v_1\in A{\setminus } V_0$ then we have two cases: if there exist $u_1\in B,v_2\in A$ such that $(u_1,v_2)\notin E_0$, we pick an arbitrary $u_2\in B$ and flip the edges $\{u_1,u_2\}\times \{v_1,v_2\}$. This produces a valid dominating Eulerian subgraph that contains $v_1$. In the final case, all edges of $A\times B$ not incident on $v_1$ are used in $E_0$. Then, picking two arbitrary $u_1,u_2\in B$ and a vertex $v_2\in A$ and flipping the edges $\{u_1,u_2\}\times \{v_1,v_2\}$ produces a valid solution that includes $v_1$. We can conclude that $A\subseteq V_0$.

For the second property, observe that if $E_0$ does not use any edges of $A\times B$ then we can add an arbitrary cycle to $E_0$ using edges of $A\times B$ producing a valid solution.       $\square$

Lemma 6

Let $G(V,E)$ be a graph and $A,B\subseteq V$ with $A,B$ disjoint sets, $|A|,|B|\ge 5$ and $A\times B \subseteq E$. Let $C=\{c_1,c_2,c_3\}$ be a set of three new vertices. Consider the graph $G'(V',E')$ where $V'=V\cup C$ and $E'=(E{\setminus } A\times B)\cup (A\times C) \cup (B\times C)$. Then $G'$ has an edge-Hamiltonian cycle if and only if $G$ does.

Proof

For the first direction, suppose that $G$ has a dominating Eulerian subgraph $G_0(V_0,E_0)$. We will now describe a dominating Eulerian subgraph $G_0'(V_0',E_0')$ of $G'$. We set $V_0'= V_0\cup C$, which is clearly a vertex cover of $G'$. To construct $E_0'$, we begin with the set of edges $E_0{\setminus } (A\times B)$. Now, we need to consider the bipartite subgraph $G^{A\cup B}_0$ of $G_0$ induced by $A\cup B$. In this subgraph, there will be an even number of vertices of odd degree. For each such vertex $u$, we add an edge in $G'_0$ from $u$ to each of the vertices of $C$. This ensures that $u$ will still have an odd degree in the subgraph $G'^{A\cup B\cup C}_0$ of $G'_0$ induced by $A\cup B\cup C$. Furthermore, all vertices of $C$ in $G'_0$ should currently have even degree. Let $D$ be the set of remaining vertices of $G^{A\cup B}_0$, with even degree. If $|D|$ is a multiple of 3, we connect a third of these vertices with $c_1$ and $c_2$, a third with $c_1$ and $c_3$ and a third with $c_2$ and $c_3$. If $|D|=2\mathrm{{\ mod\ }}3$, then we connect two vertices of $D$ with $c_1, c_2$ and for the rest we act as in the previous case. If $D=1\mathrm{{\ mod\ }}3$, and $|D| \ge 4$, we connect four vertices of $D$ with $c_1, c_2$ and act as before for the rest. Last, for the case that there is only one vertex of even degree, we connect it to $c_1$ and $c_2$ while at the same time we remove the edges $(v,c_1)$ and $(v,c_2)$ for some other vertex $v$ of odd degree. Observe that this process ensures that in the end all vertices of $A,B$ have degree in $G'^{A\cup B\cup C}_0$ with the same parity as in $G^{A\cup B}_0$ and all vertices of $C$ have even degree in $G'_0$. Furthermore, the constructed graph is always connected because the bipartite subgraph is sufficiently large.

For the converse direction, suppose we have a dominating Eulerian subgraph $G_0'(V_0',E_0')$ of $G'$. By Lemma 5, because $C,(A\cup B)$ form two parts of a sufficiently large complete bipartite subgraph we can assume that $(A\cup B\cup C)\subseteq V_0'$.

We build a dominating Eulerian subgraph $G_0(V_0,E_0)$ of $G$ as follows. First, $V_0=V_0'{\setminus } C$, which is a vertex cover of $G$. Let $E_C$ be the set of edges of $E_0'$ incident on $C$. It must be the case that $|E_C|$ is even, since all vertices of $C$ have even degree in $G_0'$ and $C$ is an independent set. We start building $E_0$ by including all the edges of $E_0'{\setminus } E_C$. We will now go through two phases of “fixing” $E_0$ by adding to it edges of $A\times B$.

Initially, we concentrate on making all degree parities even. We will say that we flip an edge $e$ to mean that, if $e\in E_0$ then we remove it from $E_0$, otherwise we add it to $E_0$. Observe that, for our current selection of $E_0$, the number of vertices of $A\cup B$ with odd degree in $G_0$ is even. This is a consequence of the fact that $|E_C|$ is even and that all vertices have even degree in $G_0'$. As long as there exist two vertices $u,v$ of $A\cup B$ with odd degree in $G_0$, select a shortest path connecting $u$ and $v$ in $G$ and flip its edges. This will only change the parity of the degree of $u$ and $v$ in $G_0$. Repeating this process will eventually produce a set $E_0$ that makes the degree of all vertices even.

We now need to augment $E_0$ to make sure that $G_0$ is connected. It is not hard to see that if $G_0$ is not connected, there must be two vertices of $A\cup B$ in different components (otherwise, we could find a disconnected component in $G_0'$). Our intermediate goal is to create a solution where each part (excluding possibly at most one vertex) belongs as a whole in one connected component. Starting from part $A$, let’s assume that it doesn’t belong as a whole in one component, in other words assume that there exist two vertices $v_1,v_2$ such that $v_1, v_2$ are in different components.

One of $v_1, v_2$ should have at least two neighbors in $B$, otherwise we can find two common non-neighbors $u_1, u_2$ and add the edges of $\{u_1,u_2\}\times \{v_1,v_2\}$ to $E_0$ to obtain a valid solution with fewer components. So assume that $v_2$ has at least two neighbors in $B$, $u',u''$.

Now, for each additional vertex $v_3$ of $A$, if $v_3$ is not at the same connected component as $v_2$, we can add all edges between $\{u', u''\}$ and $\{v_1,v_3\}$ and obtain a solution with fewer connected components. Therefore, every vertex of $A$ except for $v_1$ belongs to the same connected component as $v_2$.

With similar reasoning, we can conclude that every vertex of $B$ but (possibly) one vertex (call this $u_1$ if it exists) also belongs in one connected component. Additionally, we can easily conclude that, in the case the big components from each part are disconnected, we can connect them by joining two pairs of vertices from each of them.

We are now almost done. We describe the process to attach $v_1$ to the big connected component ($u_1$, if it exists, can be handled in a similar way). If there exists at least one vertex of the big component in $A$ with two non-neighbors in $B$, then we completely join these three vertices together with $v_1$ in a $K_{2,2}$. In the other case, all vertices of $A$ from the big component have at most one non-neighbor in $B$. This means that the big component is very well-connected, so we can take an arbitrary vertex of $A$ together with two arbitrary vertices of $B$ and flip all edges between them while adding all edges from $v_1$ to these two vertices of $B$. After performing this step, the connectivity of the graph is increased.       $\square$

We are now almost ready to proceed with our algorithm. To simplify presentation, we will only apply Lemma 6 to subgraphs which are at least as large as $K_{7,7}$. Observe that in such a case, $G'$ has strictly fewer edges than $G$. It is then clear that the reduction is making progress and after a bounded number of applications we get a graph with no large complete bipartite subgraphs.

There is, however, one problem that remains. We must also show that we can apply Lemma 6 repeatedly without increasing the graph’s clique-width. If we cannot guarantee this, then, even though we will have eliminated large $K_{t,t}$ subgraphs, we will not be able to invoke Theorem 1 in the end. We therefore have to take care to only apply the reduction rule in some specific situations. For this, we will have to work with the given clique-width expression of $G$.

Our first step is to handle an obvious part of the given clique-width expression where large bipartite subgraphs are constructed, namely, the join operation.

Lemma 7

Given a graph $G$ and a clique-width expression with $k$ labels, it is possible to produce in polynomial time a graph $G'$ and a clique-width expression with $k+2$ labels such that:

• 1. $G$ has an edge-Hamiltonian cycle if and only if $G'$ does

• 2. For every join operation in the expression of $G'$, one of the two involved sets of vertices contains at most $6$ vertices.

Unfortunately, Lemma 7 is not enough to guarantee the elimination of large complete bipartite subgraphs, since these may also be constructed gradually. However, eliminating big joins gives our clique-width expression a certain structure which we can leverage to deal with the remaining bi-cliques efficiently.

Lemma 8

Given a graph $G(V,E)$ and a clique-width expression with $k$ labels and the property that for all join operations one involved set has size at most $6$, we can in polynomial time produce a graph $G'$ with clique-width $k+2$ such that $G'$ does not contain $K_{21k,21k}$ as a subgraph.

We can now describe our algorithm. Given a graph $G$ and a clique-width expression with $k$ labels, we first invoke the algorithms of Lemmata 7,8. We are thus left with a graph with clique-width at most $k+4$ and no complete bipartite subgraph larger than $K_{t,t}$ for $t=O(k)$. By Theorem 1, this graph has treewidth $O(k^2)$. We can now apply an FPT algorithm to obtain a reasonable tree decomposition (see e.g. [2]) and then invoke Theorem 5.

Theorem 6

Given a graph $G$ and a clique-width expression with $k$ labels, there exists an algorithm that decides if $G$ has an edge-Hamiltonian cycle in time $k^{O(k^2)} n^{O(1)}$.