Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs

Let ${𝒫}_0=(V_1^0,\mathrm{\dots },V_t^0)$ be the $\kappa$-partition obtained in Theorem 5, so that $G_{{𝒫}_0}$ has maximum degree $\mathrm{\Delta }$ and treewidth $O(n^{1-1/d})$. This partition can be computed in polynomial time, and a tree decomposition of width $O(n^{1-1/d})$ in time $2^{O(n^{1-1/d})}$. We now refine each part $V_i^0$ of ${𝒫}_0$ using the following key claim. Let $g:\mathbb{N}\to \mathbb{N}$ be a function to be set later.

We first construct a separator tree $T$ for $G[X]$. This is a rooted tree defined as follows. If $G[X]$ has no vertex separator of size at most $g(\kappa )$, then $T$ consists of a single leaf, which is also the root, and whose label is $X$. Otherwise, let $S\subseteq X$ be a vertex separator of $G[X]$ of size at most $g(\kappa )$, and let $X_1,\mathrm{\dots },X_{\mathrm{\ell }}$ be the vertex sets of the connected components of $G[X\setminus S]$, where $\mathrm{\ell }\ge 2$. For each $i\in \{1,\mathrm{\dots },\mathrm{\ell }\}$, recursively construct a separator tree $T_i$ for $G[X_i]$. Then $T$ is obtained by creating a new root node labelled with $S$ and making it adjacent to the roots of $T_1,\mathrm{\dots },T_{\mathrm{\ell }}$.

By construction, every leaf of $T$ is labelled with a set $C\subseteq X$ such that $G[C]$ has no separator of size at most $g(\kappa )$; that is, each $G[C]$ is $g(\kappa )$-connected.

Furthermore, $T$ has at most $\kappa$ leaves. Indeed, suppose for contradiction that $T$ had at least $\kappa +1$ leaves $C_1,\mathrm{\dots },C_{\kappa +1}$. Since the labels of distinct leaves lie in distinct connected components after removing all separators encountered on their respective root–leaf paths, they are pairwise non-adjacent. Thus picking one vertex from each $C_i$ yields an independent set of size $\kappa +1$, which is a contradiction with the existence of a clique partition of size $\kappa$.

Since every internal node has at least two children and the tree has at most $\kappa$ leaves, it follows that $T$ has at most $\kappa -1$ internal nodes. Each internal node is labelled with a separator of size at most $g(\kappa )$, so the union $X^{\prime }$ of those labels satisfies $|X^{\prime }|⩽(\kappa -1)g(\kappa )$.

Finding a vertex separator of size at most $g(\kappa )$ can be done in time ${|X|}^{g(\kappa )}$. Since $T$ contains at most $2\kappa -1$ nodes, this operation is performed at most $2\kappa -1$ times. Hence the total running time for constructing $T$ is $(2\kappa -1){|X|}^{g(\kappa )}$. Since $X^{\prime }\subseteq X$, the set $X^{\prime }$ admits a partition into at most $\kappa$ cliques. As $|X^{\prime }|⩽(\kappa -1)g(\kappa )$, one can find such a partition by brute force in time ${\kappa }^{(\kappa -1)g(\kappa )}$, by enumerating all partitions of $X^{\prime }$ into $\kappa$ (possibly empty) parts. Finally, note that the leaf labels of $T$, together with the clique partition of $X^{\prime }$, yield a partition of $X$ into at most $2\kappa$ parts, each of them being either a clique or $g(\kappa )$-connected.$\mathrm{⊲}$

Applying Claim 11 to each $V_i^0$ yields a refined partition of $V(G)$ into at most $2\kappa$ subsets per class, each of which induces a clique or a $g(\kappa )$-connected subgraph. Let $𝒫$ denote the resulting partition of $V(G)$, and consider the contraction $G_{𝒫}$.

Since each $V_i^0$ was replaced by at most $2\kappa$ subsets, $G_{𝒫}$ has maximum degree at most ${\mathrm{\Delta }}^{\prime }:=(\mathrm{\Delta }+1)\cdot 2\kappa$. Moreover, its treewidth remains $O(n^{1-1/d})$, since $\kappa$ is a constant.

Finally, fix $\lambda >{\mathrm{\Delta }}^{\prime }$ as large as desired (but constant), and fix $g(\kappa )$ large enough such that $g(\kappa )⩾\max (\kappa +3,10)\cdot 3\lambda$. Then each part of $𝒫$ is either a clique or Hamiltonian $\lambda$-linked by Lemma 8, which proves the theorem.

Note that $𝒫$ can be computed in polynomial time: the partition ${𝒫}_0$ is obtained in polynomial time, and by Claim 11, the refinement of each $V_i^0\in {𝒫}_0$ can also be computed in polynomial time. Moreover, a tree decomposition of $G_{𝒫}$ of treewidth $O(n^{1-1/d})$ can be obtained from a tree decomposition of $G_{{𝒫}_0}$ by replacing each vertex $V_i^0$ with the vertices of its refinement in $𝒫$. Since the treewidth remains $O(n^{1-1/d})$, such a decomposition can be computed in time $2^{O(n^{1-1/d})}$. $◀$

We give here an algorithm for Hamiltonian Cycle and explain at the end how to obtain that for Hamiltonian Path. According to Theorem 10, for some constants $\mathrm{\Delta }$ and $\lambda$ with we can compute a $\lambda$-linked partition $𝒫=(V_1,\mathrm{\dots },V_t)$ of $G$ and a tree decomposition of $G_{𝒫}$ in time $2^{O(n^{1-1/d})}$. In order to be able to apply Lemma 13, we define $G^{\times }$ as the graph obtained by turning each $V_i$ into a clique (i.e., by adding all missing edges inside each $V_i$). We call the edges of $E(G^{\times })\setminus E(G)$ the red edges.

Compute the edge sets from Lemma 13, and call these blue edges. Let $H$ be the graph obtained from $G^{\times }$ by removing every vertex not incident to a blue edge, except for one special vertex $v_i$ per part $V_i$ (if such a vertex exists). Denote by $V_i^H$ the set of vertices of $V_i$ that remain in $H$. Since $G_{𝒫}$ has maximum degree at most $\mathrm{\Delta }$, at most $4\mathrm{\Delta }{(2\mathrm{\Delta }-1)}^2$ vertices from each $V_i$ are incident to blue edges, so $|V_i^H|⩽4\mathrm{\Delta }{(2\mathrm{\Delta }-1)}^2+1$. Observe that $H$ is a subgraph of the lexicographic product of $G_{𝒫}$ with a clique of constant size (depending on $d$ only), hence its treewidth is $O(n^{1-1/d})$.

We now prove that $G$ admits a Hamiltonian cycle if and only if $H$ does.

Suppose that $G$ has a Hamiltonian cycle. Then so does $G^{\times }$ as it is a supergraph of $G$. By Lemma 13, $G^{\times }$ admits a Hamiltonian cycle $C$ that uses at most two blue edges between any $V_i$ and $V_j$, that belong to $E_{i,j}$. Removing from $C$ any vertex $v\in V_i\setminus V_i^H$ preserves Hamiltonicity in $H$ (as $V_i^H$ is a clique in $H$, and the neighbors of $v$ in $C$ must belong to $V_i$, otherwise $v$ would be adjacent to a blue edge), hence $H$ has a Hamiltonian cycle.

Conversely, suppose that $H$ has a Hamiltonian cycle $C$. We reconstruct a Hamiltonian cycle of $G$ as follows. For each $i\in [t]$, if $G[V_i]$ is a clique, we can insert the missing vertices of $V_i\setminus V_i^H$ along $C$. Indeed, if $V_i^H$ contains a special vertex $v_i$, then $C$ must contain an edge $u{v}_i$ with $u\in V_i$, and thus all vertices of $V_i\setminus V_i^H$ can be inserted between $u$ and $v_i$ in $C$. If $V_i^H$ do not contain a special vertex, then $V_i^H=V_i$ and $C$ already contain all vertices of $V_i$.

If instead $G[V_i]$ is Hamiltonian-$\lambda$-linked, fix an orientation of $C$ and let $s_1,\mathrm{\dots },s_m$ be the vertices of $V_i$ where $C$ enters $V_i$, and $t_1,\mathrm{\dots },t_m$ where it exits. Observe that $2m⩽2\mathrm{\Delta }$ as one can map each $s_j$ (resp. $t_j$) to the unique blue edge that $C$ uses to enter (resp. exit) $V_i^H$, and $C$ uses at most $2\mathrm{\Delta }$ blue edges adjacent to $V_i^H$ (at most two blue edges per adjacent part of $V_i$ in $G_{𝒫}$). Since $G[V_i]$ is Hamiltonian-$\lambda$-linked with $\lambda >\mathrm{\Delta }$, there exist $m$ vertex-disjoint paths in $G[V_i]$ covering $V_i$ and connecting each $s_j$ to $t_j$. Replacing the subpaths of $C$ within $V_i$ by these paths yields a Hamiltonian cycle of $G$. See Figure 2 for an illustration.

To sum up, we reduced the problem to that of deciding whether $H$ has a Hamiltonian cycle. Recall that $H$ has treewidth $O(n^{1-1/d})$. This can be done in time $2^{O(n^{1-1/d})}$ using Theorem 14 on the tree decomposition of $H$ computed above. Each local reconstruction inside a part $V_i$ can be carried out using the algorithm of Lemma 8 in polynomial time.

With minor adjustments, Lemma 13 also applies to the Hamiltonian Path problem. More precisely, if $G$ admits a Hamiltonian path, one can construct a graph $G^{\prime }$ by adding a special edge between the two endpoints of that path. The resulting graph $G^{\prime }$ admits a clique partition of bounded degree, and thus Lemma 13 applies to it. The Hamiltonian cycle obtained in $G^{\prime }$ may include the special edge; removing this edge then yields a Hamiltonian path in the original graph $G$. Then, the very same proof carries over to Hamiltonian Path, yielding an algorithm with identical running time. $◀$

Let ${\{O_v\}}_{v\in V(G)}$ be a representation of $G$ with similarly sized $\beta$-fat objects in ${ℝ}^d$. Let $v\in V(G)$. Observe than since the object associated to every neighbor of $v$ intersects $O_v$, and these objects are $\beta$-fat, there is a $d$-dimensional hypercube of side length $6\beta$ that delimits a region containing the objects of $v$ and all its neighbors. More generally for any integer $r⩾1$, all the vertices at distance at most $r$ from $v$ in $G$ have their objects in the region of ${ℝ}^d$ enclosed by a $d$-dimensional hypercube of side length $c_{\beta }r$, for some constant $c_{\beta }$ depending only on $\beta$.

This hypercube can be partitioned into at most $c_{\beta }^d{r}^d$ smaller hypercubes of unit side length. Since the objects are $\beta$-fat, the object $O_u$ associated to each $u\in V(G)$ contains a ball of radius 1. Let us denote by $z_u$ the center of such a ball. Observe that if a smaller hypercube contains $z_u$ and $z_{u^{\prime }}$ for some $u,u^{\prime }\in V(G)$, then $O_u$ and $O_{u^{\prime }}$ intersect and so $u$ and $u^{\prime }$ are adjacent. Hence each such smaller hypercube contains at most $\mathrm{\Delta }+1$ points of the form $z_u$ for $u\in V(G)$ (whose associated vertices form a clique of order at most $\mathrm{\Delta }+1$). Therefore, the ball $B_G(v,r)$ contains at most $c_{\beta }^d(\mathrm{\Delta }+1)\cdot r^d$ vertices, as claimed. $◀$

We will use the following lemma showing that in graphs of polynomial growth, one can select a subset of vertices inducing connected components of radius $O(k\log k)$ and that has good probability of containing an unknown subset $X\subseteq V(G)$ of size at most $k$.

We then give a low-treewidth pattern covering lemma for intersection graphs of similarly sized fat objects and bounded maximum degree, with diameter polynomial in $k$. The proof, available in the long version, follows essentially the same clustering procedure as in [12]. Roughly speaking, the idea is to construct a collection of disjoint clusters in the graph, where each cluster induces a subgraph of small treewidth, and then add a small number of vertices that are adjacent to these clusters in order to ensure connectivity between them. The main difference with [12] lies in the analysis of the treewidth of the clusters, which can be improved in the case of geometric graphs.

We begin by computing, in polynomial time, the $\lambda$-linked partition $𝒫=(V_1,\mathrm{\dots },V_t)$ guaranteed by Theorem 10, such that $G_{𝒫}$ has maximum degree $\mathrm{\Delta }$, for some constants $\lambda$ and $\mathrm{\Delta }$ such that . Let $G^{\times }$ denote the graph obtained from $G$ by turning each $V_i$ into a clique, that is, by adding all missing edges inside each $V_i$. Again, the edges in $E(G^{\times })\setminus E(G)$ are called red edges.

We apply Lemma 19 to the pair $(G^{\times },𝒫)$, yielding the marking function $𝖬$ defined on $V(G^{\times })$. From this, we build the weighted graph $H$ as follows: for each $1⩽i⩽t$, let $U_i:=V_i\setminus 𝖬(i)$, and contract all vertices in $U_i$ into a single vertex $v_i$ with weight $w_i:=|U_i|$. Whenever $U_i\ne \mathrm{\varnothing }$, define $Q_i:=𝖬(i)\cup \{v_i\}$. If $U_i=\mathrm{\varnothing }$, do not create vertex $v_i$ and define $Q_i:=𝖬(i)$. All remaining vertices (the marked ones) receive weight $1$. Note that $Q_i$ is a clique in $H$ for all $1⩽i⩽t$.

We now define two auxiliary graphs derived from $H$:

1. 1.

   $H^{\prime }$ is obtained from $H$ by deleting every edge $v_{i}u$ with $u\in V_j$ and $j\ne i$.

2. 2.

   $H^{\times }$ is obtained from $H$ by adding, for every , all edges between $Q_i$ and $Q_j$ whenever there exists an edge $uv\in E(H^{\prime })$ with $u\in Q_i$ and $v\in Q_j$. Note that, for any $u,v\in Q_i$, $u$ and $v$ are true twins in $H^{\times }$, meaning that $N_{H^{\times }}[u]=N_{H^{\times }}[v]$. Moreover, $H^{\prime }$ is a subgraph of $H^{\times }$.

See Figure 3 for an illustration of the graphs $G$, $G^{\times }$, $H$, $H^{\prime }$ and $H^{\times }$. We first prove that $H^{\times }$ is the intersection graph of similarly sized fat objects in ${ℝ}^d$.

Let $𝒪={\{O_v\}}_{v\in V(G)}$ be a geometric representation of $G$ with $d$-dimensional similarly sized $\beta$-fat objects. For each $i$, let $O_i={\bigcup }_{v\in V_i}{O}_v$. Since $V_i$ is $\lambda$-linked, the diameter of $O_i$ is bounded by $O(\beta )$ by Remark 12, and $O_i$ contains a ball of radius $1$ (as each $O_v$ does). We represent every vertex $u\in Q_i$ by the same object $O_i$.

Note that for each $1⩽i⩽t$, the objects representing $Q_i$ pairwise intersect, since they are all represented by the same geometric object. Moreover, for any , the objects $O_i$ and $O_j$ intersect whenever there exist vertices $u\in V_i$ and $v\in V_j$ such that $O_u$ and $O_v$ intersect. It follows that $H^{\times }$ is indeed the intersection graph of $\{O_u:u\in V(H^{\times })\}$. In addition, its degree is bounded by ${\mathrm{\Delta }}^{\prime }={\mathrm{\Delta }}^{O(1)}$, as each $O_i$ intersects only a bounded number of other regions corresponding to adjacent parts in $G_{𝒫}$. $\mathrm{⊲}$

We now show that $G$ has a long path if and only if $H^{\prime }$ does.

Suppose that $G$ contains a path $P$ on $k$ vertices with endpoints $x$ and $y$. Since $G$ is a subgraph of $G^{\times }$, $P$ is also a path in $G^{\times }$. By Lemma 19, $P$ can be modified into a path $P^{\prime }$ such that for each $i$, $P^{\prime }$ contains all vertices in $(V(P)\cap V_i)\setminus 𝖬(i)$ consecutively along $P^{\prime }$, and we call $P_i$ such a subpath. By contracting each such $P_i$ into a single vertex $v_i$, we obtain a path $P_H$ in $H^{\prime }$ whose total weight equals $|V(P)|⩾k$.

Conversely, let $P_H$ be a weighted path in $H^{\prime }$ of total weight at least $k$. For each contracted vertex $v_i$ of weight $w_i$, we expand it into an arbitrary path of $w_i$ distinct vertices from $U_i$. The two vertices (if they exist) adjacent to $v_i$ in $P_H$ must belong to $𝖬(i)$ by definition of $H^{\prime }$, so the resulting expanded path $P^{\prime }$ exists in $G^{\times }$ and has at least $k$ vertices.

It remains to transform the path $P^{\prime }$ in $G^{\times }$ into a path in $G$. Currently, $P^{\prime }$ may use red edges inside some $V_i$ that is not a clique in $G$, but each $G[V_i]$ is Hamiltonian $\lambda$-linked. Fix $i$ such that $G[V_i]$ is Hamiltonian $\lambda$-linked, and let $s_1,\mathrm{\dots },s_m$ be the vertices of $V_i$ where $P^{\prime }$ enters $V_i$, and $t_1,\mathrm{\dots },t_m$ the vertices where it exits. Since $P^{\prime }$ must enter and exit through marked vertices, we have $m={\mathrm{\Delta }}^{O(1)}$. If $\lambda$ is chosen so that $\lambda >m$, there exist $m$ vertex-disjoint paths ${\{P_{i,j}\}}_{1⩽j⩽m}$ covering all vertices of $V_i$, each connecting $s_j$ to $t_j$. Replacing each subpath between $s_j$ and $t_j$ in $P^{\prime }$ by $P_{i,j}$ yields a new path with at least the same number of vertices, and without using red edges. Performing this replacement for every part $V_i$ such that $G[V_i]$ is Hamiltonian $\lambda$-linked yields a path on at least $k$ vertices in $G$. This construction can be carried out in polynomial time by Lemma 8. $\mathrm{⊲}$

We now describe the algorithm. Suppose that $G$ has a path $P$ with $k$ vertices. We apply successively Lemma 17 and Lemma 18 to $H^{\times }$ (which, by the previous claim, is the intersection of similarly-sized fat objects in ${ℝ}^d$, and has bounded maximum degree) to obtain a set $A\subseteq V(H^{\times })$ such that:

1. 1.

   the treewidth of $H^{\times }[A]$ is $O(k^{1-1/d}\log k)$;

2. 2.

   with probability at least $2^{-O(k^{1-1/d}{\log }^{2}k)}$, we have $V(P)\subseteq A$.

Since $H^{\prime }$ is a subgraph of $H^{\times }$, $H^{\prime }[A]$ also has treewidth $O(k^{1-1/d}\log k)$. Then, one can find a path on $k$ vertices in $H^{\prime }[A]$ using Proposition 20 in time $2^{O(k^{1-1/d}\log k)}\cdot n^{O(1)}$. Repeating this process $2^{O(k^{1-1/d}{\log }^{2}k)}$ times ensures constant success probability. If a path on $k$ vertices is found in $H^{\prime }$, we construct in polynomial time a path on $k$ vertices of $G$ using Claim 22. If no such path is found after all repetitions, the algorithm reports that $G$ has no path on $k$ vertices. $◀$