Multivariate Exploration of Metric Dilation

Throughout this paper, we deal with the shortest-path metric derived from an unweighted graph, unless otherwise mentioned.¹¹1Any metric can be derived from an edge weighted graph. Thus, our assumption represents a simplification. For an edge weighted graph $H$, let $d_H(u,v)$ denote the weighted shortest path distance in the graph $H$ between two vertices $u$ and $v$. Additionally, we use ${\mathrm{𝗁𝗈𝗉}}_H(u,v)$ to denote the length of the shortest path between $u$ and $v$ when we forget the edge weights. In other words, this denotes the length of the shortest path in $H$ when all edges receive weight $1$. We will use $d_H$ and ${\mathrm{𝗁𝗈𝗉}}_H$ only when $H$ is edge weighted; otherwise, both $d_H$ and ${\mathrm{𝗁𝗈𝗉}}_H$ represent the same thing. Throughout the article, the metric $ℳ$ will be derived from an undirected unweighted graph $\mathrm{\Gamma }=(V,E)$. That is, the vertices of the metric correspond to the vertices of $\mathrm{\Gamma }$, and $d_M(u,v)$ is assigned the shortest path distance in $\mathrm{\Gamma }$, between $u$ and $v$. Observe that $d_M(u,v)=d_{\mathrm{\Gamma }}(u,v)={\mathrm{𝗁𝗈𝗉}}_{\mathrm{\Gamma }}(u,v)$. We will use $(G,\mathrm{\Gamma },k)$ as an instance of Dilation $t$-Augmentation problem. Since $ℳ$ is derived from $\mathrm{\Gamma }$, for ease of notation, we use $d_{\mathrm{\Gamma }}(u,v)$ instead of $d_M(u,v)$. Furthermore, recall that $G$ is embedded in the metric space $ℳ$ derived from $\mathrm{\Gamma }$. That is, $G$ is an edge-weighted graph, where the weights assigned to the edges of $G$ represent the distances in $\mathrm{\Gamma }$ between their end-points. That is, $w(u,v)=d_{\mathrm{\Gamma }}(u,v)$ and $d_G(u,v)$ denote the weighted shortest path distance in $G$.

The starting point of our research is the result of Peleg and Schäffer [19] that Dilation $t$-Augmentation is NP-hard for $t=2$, where $G$ is an empty graph and the metric $ℳ$ is derived from an undirected graph $\mathrm{\Gamma }$. So, a natural question is whether this special subcase is FPT. Starting with this question, we trace the boundaries of the Dilation $t$-Augmentation problem by instantiating different graph families to which $\mathrm{\Gamma }$ can belong or by instantiating different graph families to which $G$ can belong. Our results consist of the following.

It is important to note that the family of ${𝒦}_{d,d}$-free graphs includes trees, planar graphs, graphs that exclude a fixed graph $H$ as a minor, graphs of bounded expansion, nowhere dense graphs, and graphs of bounded degeneracy.²²2For a formal definition of many of these graph classes, we refer to standard texts on graph theory, e.g., Diestel [5]. We refer to Table 1 for a quick reference of all the results shown in this article.

Our algorithmic results are based on the structural interaction between $\mathrm{\Gamma }$ and $G$. We start by defining the notion of conflict pairs (a pair $(u,v)$ in $G$ such that $d_G(u,v)>t\cdot d_{\mathrm{\Gamma }}(u,v)$) and show that to resolve these pairs it suffices to focus on those pairs that are adjacent in $\mathrm{\Gamma }$ (that is, $(u,v)\in E(\mathrm{\Gamma })$). We call them adjacent conflicts. Resolving adjacent conflict pairs is the key to our results, both algorithms and hardness.

Our main result regarding Dilation $2$-Augmentation when $G$ is ${𝒦}_{d,d}$-free is given in Section 3. Our algorithm can be broadly divided into three separate phases. First, in Section 3.1 we define the notion of a conflict graph and bound the size of the minimum vertex cover in this graph using the restrictions imposed on the solution for Dilation $t$-Augmentation in the special case of $t=2$. Then, in Section 3.2, we analyze the interplay between the bounded-size vertex cover, along with the structural properties of $G$ due to the fact that it is ${𝒦}_{d,d}$-free, and use it to design a recursive algorithm that tries to guess a certain kind of edges that must belong to any solution in a yes-instance. At the leaves of this recursive procedure, we can upper bound the total number of vertices involved in conflicts. Nevertheless, we cannot get rid of all other vertices since they may be crucial for certain shortest paths. Finally, in Section 3.3 we bound the size of the instance by carefully eliminating a subset of conflict-free vertices, at which point we can enumerate all possible solutions. For the other two algorithmic results, we obtain a small set of $V$ that contains all the end-points of edges of the solution. The hardness results are shown via parameter preserving reductions from known W-hard problems, using classical gadget constructions. The details of the results/statements marked with $\mathrm{♠}$ can be found in the full version of the paper [2].

We first define a conflict graph $ℂ$ on the set of vertices $V(G)$, which captures all adjacent conflicts. We place an edge between two vertices $u$ and $v$ in $ℂ$ if and only if $u$ and $v$ are in adjacent conflict with each other. Note that $V_c$ (the set of vertices present in adjacent conflicts) is exactly the set of vertices with degree at least one in $ℂ$. The next result shows that every edge in $E(ℂ)$ intersects some edge of a dilation $2$-augmentation set $S$.

Lemma 3 allows us to bound the size of a minimum vertex cover (set of vertices that intersects all the edges) of $ℂ$. To do so, we propose the next reduction rule and prove its correctness (or safety).

First, we use a polynomial-time algorithm (e.g., [7]) to find the maximum matching $M$ in $ℂ$ and apply Reduction Rule 1. Notice that if the reduction rule 1 is not applicable, then $|M|\le 2k$, which implies that it has a vertex cover of size at most $4k$ – in particular, we can take the set of end-points of the edges of in $M$ to be such a vertex cover, call it $R$.

Let $I=V\setminus R$. Note that $I$ induces an independent set in $ℂ$, but not necessarily in $G$. Next, we bound the degree of each vertex in $R$ in $ℂ$. This will imply that the number of conflict pairs is bounded.

The set $R$ is at most of size $4k$. For our algorithm at this stage, we “guess the edges of $S$ that have both end-points in $R$”. This results in an equivalent annotated instance, which is now formalized. We first define an “annotated” instance of the problem. An example of the annotated version of the problem is given by the tuple $(G^{\prime },\mathrm{\Gamma },k^{\prime },R^{\prime })$, where we also provide a vertex cover $R^{\prime }$ of the corresponding conflict graph, which is used mainly for book keeping purposes. The task is still to find a dilation $2$-augmentation set $S$ of size at most $k^{\prime }$. Here, we are not allowed to add an edge to a solution that does not have an end-point outside $R$.

Let ${\overline{E}}_R$ be the set of non-edges in $G[R]$. For every subset $\mathrm{\varnothing }\subseteq E_j\subseteq {\overline{E}}_R$ of size at most $k$, we create an instance ${ℐ}_j$ of the annotated problem, as follows: ${ℐ}_j≔(G_j,\mathrm{\Gamma },k_j,R)$ where $G_j=G+E_j$ and $k_j=k-|E_j|$. The following lemma is immediate.

From now on, we assume that we have an annotated instance of Dilation $2$-Augmentation. That is, $(G,\mathrm{\Gamma },k,R)$ is an instance of Dilation $2$-Augmentation and we are seeking a dilation $2$-augmentation set $S$ such that for any edge $(x,y)$ in $S$, $|\{x,y\}\cap R|\le 1$. That is, every edge added must contain at least one end-point that does not belong to $R$.

We now describe how to solve the annotated version of the problem. As a first step, we give a recursive algorithm such that at the end we obtain instances such that the size of $V_c$ gets upper-bounded by a function of $k$ and $d$ alone. To this end, and to make it easier to understand, we adapt the following technical definition of [3] in the context of our problem.

We now give a sequence of FPT Turing reductions to solve the problem. At a high level, we will iterate over the vertices in $R$ that have high degrees in $ℂ$, and at each step we will add at least one vertex from $I$ to $R$, and at least one new edge to $G$. Thus, in each step, the budget $k$ reduces by at least one. At least one of the resulting instances will correspond to a “correct” set of choices. Note that initially the size of $R$ is at most $4k$; however during the sequence of Turing FPT reductions, the size of $R$ may increase. Nevertheless, we will maintain the invariant that $|R|$ remains bounded by $5k$.

Let us define an auxiliary function $f$ that is useful for defining some parameters in the upcoming steps. This function is defined as follows.

It is easy to verify that $f$ satisfies the following property.

Thus, if each vertex of $R$ has at most $f(0)$ many neighbours in $I$ in $ℂ$, then eventually $|V_c|$ gets bounded by $5k\cdot f(0)$. We then move to the final step described below after Corollary 16.

Now we are in the situation where there is a vertex in $R$ with at least $f(0)+1$ neighbors in $I$ in $ℂ$. Let $v$ be such a vertex in $R$. Let $U=\{u_1,u_2,\mathrm{\dots },u_{\kappa }\}\subseteq I\cap N_{ℂ}(v)$ be the set of neighbours of $v$ in $I$, where $\kappa >f(0)$.

In the rest of the section, we describe how to solve an annotated instance $ℐ=(G,\mathrm{\Gamma },k,R)$ when the size of $V_c$ is bounded by some function of $k$ and $d$. Note that although $|V_c|\le h(k,d)$, we cannot completely forget about the vertices outside $V_c$ – since some conflicts may be resolved by using edges incident to vertices outside $V_c$. We will argue that we do not need to keep all such vertices, but it suffices to keep one representative from each “equivalence class”, which we formalize below. Note that in this last step, we do not need the vertex cover $R$.

Let $O=V(G)\setminus V_c$ denote the vertices outside $V_c$. For each $A,B\subseteq V_c$ with $A\cap B=\mathrm{\varnothing }$, let $O(A,B)$ denote the set of vertices $v\in O$ satisfying the following two properties:

1. 1.

   Set of vertices $u\in V_c$ such that $d_G(u,v)=1$ is exactly equal to $A$, and

2. 2.

   Set of vertices $w\in V_c$ such that $(v,w)\notin E(G)$, but $d_{\mathrm{\Gamma }}(v,w)=1$ is exactly equal to $B$.

We have the following observation.

For each $O(A,B)\in 𝒫$ such that $O(A,B)\ne \mathrm{\varnothing }$, we mark an arbitrary vertex $v(A,B)\in O(A,B)$. Let $U\subseteq O$ denote the set of unmarked vertices. In the following reduction rule, we eliminate all the vertices of $U$ from $G$ and $\mathrm{\Gamma }$, and then prove that it is correct.

Let $(G,\mathrm{\Gamma },k)$ be an instance of Dilation $t$-Augmentation. In this subsection, we consider the case where $\mathrm{\Gamma }$ belongs to the family of graphs of maximum degree at most $\mathrm{\Delta }$. However, there is no restriction on $G$. That is, $G$ is an arbitrary undirected graph. The idea of the proof is to identify a subset of vertices of $\mathrm{\Gamma }$ of size at most $f(k,\mathrm{\Delta },t)$ such that $V_S$ belongs to balls of radius $t$ around them. Once the set is identified, the algorithm tries all potential solutions of size at most $k$ and returns yes, if either leads to the desired solution. The hypothetical solution $S$ is of size at most $k$, and hence from Observation 19 we have $|N_{\mathrm{\Gamma }}^t(V_S)|\le 2k\cdot {\mathrm{\Delta }}^{t+1}$. First, we show that the vertices of $V_S$ are in distance $t$ from the vertices of $V_c$ in $\mathrm{\Gamma }$.

Observe that we cannot upper bound the size of $N_{\mathrm{\Gamma }}^t(V_c)$, as the size of $V_c$ may not be bounded by any function of $t,k$ and $\mathrm{\Delta }$. Next, we show a kind of converse of Lemma 20 showing that, in fact, $V_c$ is contained inside the balls of radius $t$ around $V_S$ in $\mathrm{\Gamma }$. The proof is identical to Lemma 20 and is presented separately for clarity.

Lemma 21, along with Observation 19 implies that in a yes-instance, the size of $V_c$ is bounded by $2k\cdot {\mathrm{\Delta }}^{t+1}$. Thus, if $|V_c|>2k\cdot {\mathrm{\Delta }}^{t+1}$, we say no. Now assume that $|V_c|\le 2k\cdot {\mathrm{\Delta }}^{t+1}$. Next, via Lemma 20, we have that $V_S\subseteq N_{\mathrm{\Gamma }}^t(V_c)=:Q$, say. Again, by Observation 19, $|Q|\le |V_c|\cdot {\mathrm{\Delta }}^{t+1}\le 2k\cdot {\mathrm{\Delta }}^{2t+2}$. We know we have to add at most $k$ edges between the vertices in $Q$ to resolve all the conflicts. Since the size of $Q$ is bounded by a function of $k,\mathrm{\Delta }$, and $t$, this leads to the following theorem.

Let $(G,\mathrm{\Gamma },k)$ be an instance of Dilation $t$-Augmentation. In this subsection, we consider the case where $G$ belongs to the family of graphs of maximum degree at most $\mathrm{\Delta }$. However, there is no restriction on $\mathrm{\Gamma }$. The proof strategy in this section is similar to that used for Theorem 22. As before, the idea is to identify a subset of vertices of $G$ of maximum size $f(k,\mathrm{\Delta },t)$ such that $V_S$ belongs to balls of radius $t^2$ around them.

As $|V_S|\le 2k$, the next observation follows from Observation 19.

Lemma 23 and Observation 24 together yield the following reduction rule that yields an upper bound on the size of the conflict set $V_c$.

To identify the vertices in $V_S$, we show that they lie in the balls of radius $t^2$ around $V_c$ in $G$.