Approximation Algorithms for the Generalized Point-To-Point Problem

Let $F^{\prime }$ initially be an optimum solution. While there are two components $C_1,C_2$ of $(V,F^{\prime })$ with $C_1\cap V_d\ne \mathrm{\varnothing }$ and $C_2\cap V_d\ne \mathrm{\varnothing }$ such that for some $u\in C_1$ and $v\in C_2$, add $uv$ to $F^{\prime }$. Each such addition increases the cost of $F^{\prime }$ by at most $\frac{ϵ}{n_d}\cdot OPT$ and this procedure will be executed fewer than $n_d$ times since there are initially at most $n_d$ components containing a node in $V_d$. $◀$

Of course, we may also assume, by discarding edges, that $F^{\prime }$ is a minimal solution meaning $F^{\prime }-\{e\}$ is not feasible for any $e\in F^{\prime }$. So $F^{\prime }$ consists of $m\le n_d$ vertex-disjoint trees, say $T_1,\mathrm{\dots },T_m\subseteq F$ that collectively span all of $V_d$ plus some other nodes in $V_0\cup V_s$. Any other node $v$ not in a tree has $\varphi (v)\ge 0$ and forms an isolated component of $(V,F^{\prime })$.

Next, we identify a net of nodes in the trees $T_1,\mathrm{\dots },T_m$ that will be small enough for our algorithm to guess.

Similar constructions have been considered many times before, one example is in the $(2+ϵ)$-approximation for k-MST [3]. We include a proof for completeness.

We prove this by induction on $|V(T)|$. Root $T$ at an arbitrary node $w$. The base case is when $c(w,v)\le r$ for each $v\in V(T)$. If so, we simply let $N=\{w\}$.

Otherwise, for two $u,v\in V(T)$ let $c_T(u,v)$ be the cost of the unique $u-v$ path in $T$. Pick any $v\in V(T)$ that has maximum value $c_T(w,v)$. Note $c_T(w,v)\ge c(w,v)>r$. Now let $u$ be the furthest node along the $v-w$ path such that $c_T(v,u)\le r$. Since $c(v,u)\le c_T(v,u)\le r$, then $u\ne w$. Let $p(u)$ be the parent of $u$ in $T$. By our choice of $u$ we also have $c_T(v,p(u))>r$.

Let $T_u$ denote the subtree of $T$ rooted at $u$. For any $v^{\prime }\in V(T_u)$ we have $c(v^{\prime },u)\le c_T(v^{\prime },u)\le c_T(v,u)\le r$. Let $T^{\prime }$ be the tree obtained by removing the subtree rooted at $u$ from $T$. This removes all edges of the $v-p(u)$ path, so $c(T^{\prime })\le c(T)-r$. By induction, we can find a set $N^{\prime }\subseteq V(T^{\prime })$ with $|N^{\prime }|\le 1+c(T^{\prime })/r\le c(T)/r$ such that $c(w^{\prime },N)\le r$ for each $w^{\prime }\in V(N^{\prime })$.

Finally, set $N=\{u\}\cup N^{\prime }$ and note $|N|=1+|N^{\prime }|\le 1+c(T)/r$. Every $u^{\prime }\in V(T)$ is now within distance $r$ from some node in $N$, as required. $◀$

The entire algorithm is summarized in Algorithm 1. The high-level idea is that it guesses a value $\nu$ very close to $OPT$ and then guesses the “nets” $N_1,\mathrm{\dots },N_m$ from Lemma 12 applied to each tree of the near-optimum solution $F^{\prime }$ using $r=\frac{ϵ}{4\cdot n_d}\cdot \nu$. Below, we show for the proper guess of $N_1,\mathrm{\dots },N_m$ that the sets $V_i$ obtained by the union of balls $B(v,r)$ for $v\in V_i$ are disjoint. This instance of GP2P then naturally decomposes into disjoint instances of W-k-MST-R. Supporting results demonstrating the performance of our algorithm are found below.

We first discuss the running time. The number of iterations of the outer loop is logarithmic in the ratio $c(E)/{\min }_{e}c(e)$, which is polynomial in the number of bits used to represent the costs in the instance. There are clearly only $n_d$ possible values for $m$ and the number of $m$-tuples satisfying the stated bounds is at most $n^{O(5\cdot n_d/ϵ)}$. So when $n_d$ is regarded as a constant, the total number of iterations is polynomial in the input size and, thus, the entire algorithm makes a polynomial number of calls to a k-MST-R approximation on instances with at most $n$ nodes and, otherwise, runs in polynomial time.

Towards the performance guarantee, we show for the “correct” guess of values in the loops the algorithm will perform well.

For (a), we have

For (b), if, say, $w\in V_i\cap V_j$ for some distinct $i,j$ then there would be some $u\in N_i$ and $v\in N_j$ such that

But this contradicts Lemma 11, which showed $c(u,v)>\frac{ϵ}{n_d}\cdot OPT$. Finally, (c) follows because the balls $B(v,r)$ for $v\in N_i$ collectively cover all of $V(T_i)$ and each node of $V_d$ lies on some $T_i$. $◀$

To finish the analysis, consider the iteration of the algorithm for the particular setting of $\nu$ and $T_1,\mathrm{\dots },T_m$ described in Lemma 13. With these values, the algorithm proceeds to run the k-MST-R approximations. In the instance corresponding to $V_i$, we know $T_i$ itself is a feasible solution so the returned tree $T_i^{\prime }$ satisfies $c(T_i^{\prime })\le \alpha \cdot c(T_i)$. Thus, the candidate GP2P solution found in this iteration has cost ${\sum }_{i=1}^{m}c(T_i^{\prime })\le \alpha \cdot c(F^{\prime })\le \alpha \cdot (1+ϵ)\cdot OPT$.

The Euclidean balls of radius $\delta /2\cdot \nu$ about points in $B(v,\nu )\cap N$ are disjoint by construction of $N$ and are completely contained in the Euclidean ball of radius $(1+\delta /2)\cdot \nu \le 2\cdot \nu$ about $v$. The volume a $D$-dimensional ball with radius $r$ is within an absolute constant factor of $f(R):=\frac{1}{\sqrt{D}}\cdot {\left(\frac{2\pi e}{D}\right)}^{D/2}\cdot R^D$. Therefore, $|B(v,\nu )\cap N|$ is at most a constant factor times $f(2\nu )/f(\delta /2\cdot \nu )={(4/\delta )}^D$. $◀$

The steps for guessing $N_1^{\prime },\mathrm{\dots },N_m^{\prime }$ are to first try all ways to partition $V_d$ into $m$ nonempty groups, a coarse upper bound on the number of such choices is $n_d^{n_d}$. For each such partition, let $v_1,\mathrm{\dots },v_m\in V_d$ be any particular representatives from the $m$ parts. We try all tuples $N_1^{\prime },\mathrm{\dots },N_m^{\prime }$ where each $N_i^{\prime }\subseteq B(v_i,\nu )\cap N$ such that ${\sum }_i|N_i^{\prime }|\le 17/ϵ\cdot n_d$ (as opposed to $5/ϵ\cdot n_d$ as in Lemma 13 since the radius $\delta$ is smaller). For each such tuple that passes the other requirements of Lemma 13, we partition the instance into disjoint Euclidean k-MST-R instances and approximate these with a PTAS. A coarse upper bound on the number of such tuples $N_1^{\prime },\mathrm{\dots },N_m^{\prime }$ is $O({(4/\delta )}^{D\cdot n_d})$.

Recall $V_d=\{v\in V:\varphi (v)=-1\}$ and $n_d=|V_d|$. So $V_s=V-V_d$ as no charge is zero in this case. We claim $n_d\le OPT$ and that any minimal solution has size at most $2\cdot n_d$. Thus, any minimal solution $F$ satisfies $|F|\le 2\cdot n_d\le 2\cdot OPT$, as required.

For the first bound, let $F^{\ast }$ be an optimum solution and $C$ any connected component in $(V,F^{\ast })$ that contains at least one node in $V_d$. If $C$ has, say, $n_d^C\ge 1$ nodes in $V_d$ then $C$ must contain at least $n_d^C$ nodes in $V_s$ as well. That is, $|C|\ge 2n_d^C$ so $F^{\ast }$ contains at least $2n_d^C-1\ge n_d^C$ edges in component $C$. Summing over all components that contain at least one node in $V_d$, we see $|F^{\ast }|\ge n_d$.

Now let $F$ be any minimal feasible solution. Let $C$ be any connected component of $(G,F)$ and let $F_C$ be the edges of $F$ in component $C$. If $C\cap V_d=\mathrm{\varnothing }$ then minimality of $F$ means $C$ is a single node $v$ with $\varphi (v)=+1$ (i.e. it has no edges). If $C\cap V_d\ne \mathrm{\varnothing }$, we claim $\varphi (C)=0$. If so, then $|C\cap V_d|=|C\cap V_s|$ so as $F_C$ is a tree (by minimality). Summing over all components would complete the claim that .

To see $\varphi (C)=0$, again recall $F_C$ is a tree. Further, for each $e\in F_C$ we have that deleting $e$ would produce a component with negative charge but it could not be that both components have negative charge since $\varphi (C)\ge 0$. Consider the orientation of edges that directs each edge $e$ toward the side that would have negative charge if $e$ was deleted. Since $(C,F_C)$ is a tree, the orientation of edges produces a directed acyclic graph. Let $r$ be any source node in this DAG.

View the tree $(C,F_C)$ as being rooted at $r$ and say $r$ has $m$ children. Let $C_1,\mathrm{\dots },C_m\subseteq C$ be such that $C_i$ are the nodes in the subtree under the $i$’th child of $r$. Since $C\cap V_D\ne \mathrm{\varnothing }$ and $\varphi (C)\ge 0$, we know $C$ has at least two nodes so $m\ge 1$.

By the orientation of edges, we have $\varphi (C_i)\le -1$ for each $1\le i\le m$. Therefore

which, by feasibility of $F$, means $\varphi (C)=0$. $◀$

It may be possible to get a better-than-2 approximation through a more involved approach. For example, notice in our proof $n_d\le OPT$ is only tight if all components $C$ of the optimum solution $F^{\ast }$ with $C\cap V_d\ne \mathrm{\varnothing }$ had $|C|=2$ (i.e. $F^{\ast }$ is a matching). So if the optimal solution $F^{\ast }$ has at least, say, $0.01\cdot n_d$ nodes of $V_d$ in components of size greater than 2 then any minimal solution would be a $1.99$-approximation. Otherwise, nearly all nodes of $V_d$ are in components that consist of a single edge. In this case, a maximum-size matching between $V_d$ and $V_s$ would then create components of charge $0$ that collectively include most nodes of $V_d$. One can even show there is a way to “alternate” the matching so that a greedy algorithm yields a good approximation (i.e. by alternating so our matching edges largely agree with the optimum matching edges), but efficiently finding such an alternation seems challenging.

One would reasonably wonder if instances of GP2P with unit-cost edges and $\pm 1$ charges are actually hard. Indeed, we conclude this section by showing APX-hardness.

We reduce from the Minimum Vertex Cover Problem in simple, cubic graphs which is known to be APX-hard [1]. That is, for some constants it is NP-hard to distinguish if a cubic graph on $n$ vertices has a vertex cover of size at most $\beta \cdot n$ or if all vertex covers have size exceeding $\alpha \cdot n$.

So let $G=(V,E)$ be an $n$-vertex cubic graph with $m=3n/2$ edges. We obtain a graph $H=(V^{\prime },E^{\prime })$ and set the charges of $v\in V^{\prime }$ as follows.

Initially let $H=G$ and set $\varphi (v)=+1$ for every $v\in V$. Then subdivide each edge $e$ with a single vertex $u_e$ with $\varphi (u_e)=-1$. Then for each $v$ we add new vertices $v^{+},v^{-},v_0,v_1,v_2,v_3$ and edges $\{v_{0}v,v{v}^{+},v^{+}{v}^{-},v^{+}{v}_1,v^{+}{v}_2,v^{+}{v}_3\}$. Here, $v,v^{+},v_1,v_2,v_3$ all have positive charge and $v_0,v^{-}$ have negative charge. See Figure 1 for an illustration of this process.

We claim $G$ has a vertex cover of size $k$ if and only the Graphical-GP2P instance given by $H$ and $\varphi$ has a solution of size $2n+2m+k=5n+k$. So if $G$ has a vertex cover of size at most $\beta n$ then there is a GP2P solution of size at most $(5+\beta )\cdot n$ and if all vertex covers in $G$ have more than $\alpha \cdot n$ then all solutions to this GP2P instance have size more than $(5+\alpha )\cdot n$. This shows there is no $\frac{5+\alpha }{5+\beta }$-approximation for GP2P with unit edge costs and charges $\pm 1$ unless P = NP.

To see the claim, first let $C\subseteq V$ be a vertex cover of $G$ with size $k$. To get a corresponding Graphical-GP2P solution, buy the following edges:

• $\mathrm{■}$

  For each $v\in C$, purchase $v{v}^{+}$.

• $\mathrm{■}$

  For each $v\in V$, purchase $v_{0}v$ and $v^{+}{v}^{-}$.

• $\mathrm{■}$

  For each $e\in E$, let $v$ be any endpoint of $e$ in $C$. Purchase $u_{e}v$ and any edge of the form $v_i{v}^{+}$ that was not purchased by another edge this way. Since $G$ is cubic, this is always possible.

In total, this purchases $k+2n+2m=k+5n$ edges. This can be seen to be a feasible solution by matching each negative-charged vertex with a positively-charged vertex in its component in a one-to-one fashion. Such a mapping is immediate from the construction: each $v_0$ can be matched with $v$, each $v^{-}$ can be matched with $v^{+}$, and each $u_e$ can be matched with the corresponding $v_i$ purchased in the description above.

For the converse, we first claim there is a well-structured optimal solution.

If so, then $C=\{v:v{v}^{+}\in F\}$ is a vertex cover of $G$ and $|F|=|C|+2n+2m=|C|+5n$, as required to complete the proof.

Let $F$ be an optimal solution. First observe we must have $v_{0}v\in F$ and $v^{+}{v}^{-}\in F$ for every $v\in V$ otherwise some negatively-charged node would be isolated. So in each component we must have the number of nodes of the form $u_e$ for various $e\in E$ is at most the number of nodes of the form $v_i$ for various $v\in V,i=1,2,3$. By optimality of $F$ and the fact each $v_i$ is a pendant node, we have that these counts are in fact equal in each component.

Let $\tau$ be any minimum-cost pairing of nodes $u_e,e\in E$ with nodes of the form $v_i$ lying in the same component as $u_e$. Here, the cost of pairing two nodes is the length of their shortest path using only edges in $F$. For each $e\in E$, let $P_e$ denote the corresponding shortest path from $u_e$ to $\tau (u_e)$. Finally, let $v(e)$ be the first vertex after $u_e$ along $P_e$, notice $v(e)$ corresponds to an endpoint of $e$ in the original cubic graph $G$.

Now consider an alternative pairing of the $u_e$ vertices with the $v_i$ vertices (which do not necessarily need to lie in the same component as $u_e$, for now). For each $u_e$, pair it with any vertex of the form $v{(e)}_i$ for some $i=1,2,3$ that has not been paired before. Such a pairing is possible since $G$ is cubic. Let $F^{\prime }$ be obtained by modifying $F$ in the following way. From $F$, first delete all edges of the form $v^{+}{v}_i\in F$ then add all edges of the form $v^{+}{v}_i$ where $v_i$ is paired under the new pairing.

This does not change the size of $F$. To ensure it is feasible, do the following. For each $e\in E$ such that $P$ was not initially paired with one of $v{(e)}_1,v{(e)}_2,v{(e)}_3$, it must have been that $v(e)u_{e^{\prime }}$ was the second edge along $P$ for some $e\ne e^{\prime }$ and that $v(e^{\prime })\ne v(e)$ (otherwise $P_e$ and $P_{e^{\prime }}$ both use $v(e)u_{e^{\prime }}$ but in opposite directions, meaning we can uncross the paths to get a cheaper pairing than $\tau$). So we remove $v(e)u_{e^{\prime }}$ and add $v(e)v{(e)}^{+}$ (if it was not already there). Doing so for all $e\in E$ will ensure it is now feasible since each $u_e$ can now reach the vertex it is paired with while not increasing the size of $F$ because an edge of the form $v(e)v{(e)}^{+}$ is added only after an edge of the form $v(e)u_{e^{\prime }}$ is removed. This also ensures all properties required by the claim now hold. $\mathrm{⊲}$ $◀$