4
$\begingroup$

Consider an undirected graph with two distinguished nodes $u\neq v$. How hard is it to find an $u-v$ path, such that its length is as close to the average $u-v$ path length as possible?

Formally, for a path $P$ let $\ell(P)$ denote its length (number of edges on $P$, but a weighted version may also be considered). Let $A$ denote the average length of simple $u-v$ paths: $$A= \frac{1}{N}\sum \ell(P)$$ where $N$ is the number of simple $u-v$ paths and the summation is taken over all such paths. Let us call a simple $u-v$ path $P_0$ typical if $|\ell(P_0)-A|$ is minimum.

Question: What is the complexity of finding such a typical path? Is anything known about this problem?

$\endgroup$
1
  • 1
    $\begingroup$ Does anybody know the complexity of sampling a simple $u$-$v$ path uniformly at random? That could be useful for approximating the unweighted case. $\endgroup$
    – Neal Young
    Oct 22, 2022 at 10:59

1 Answer 1

2
$\begingroup$

Lemma 1. The weighted problem is NP-hard by reduction from Partition.

Lemma 2. The unweighted problem is NP-hard by reduction from Hamiltonian Path.

Proof of Lemma 1. Given a Partition instance $(x_1, \ldots, x_n)$, construct the multigraph $G=(V,E)$ with $V=[n+1]$ and, for each $i\in [n]$, two copies of edge $(i, i+1)$, one with weight $x_i$ and the other with weight zero. Then ask for the path from $1$ to $n+1$ whose weight is as close to average over paths from $1$ to $n+1$.

By linearity of expectation, the average weight is $\sum_{i=1}^n x_i/2$, so there is a path with average weight if and only if the Partition instance is feasible.

(If desired, the multigraph can easily be converted to an equivalent graph by splitting each edge $(i, i+1)$ of weight zero into two zero-weight edges.) $~~~\Box$

Proof sketch for Lemma 2. Given a Hamiltonian Path instance $G=(V,E)$ with source $s$ and sink $t$, construct the following multigraph $G'$. Let $n=|V|$.

First, add a new, long "super-path" from $s$ to $t$ as follows. Fix some $p, q, k, \ell$ to be determined later. Add $k$ new vertices $a_1, a_2, \ldots, a_k$, with $p$ new multi-edges $(a_i, a_{i+1})$ between each consecutive pair. Add edges $(s, a_1)$ and $(a_k, t)$. This addition adds $p^k$ paths of length $k$ from $s$ to $t$.

Now add another (separate) super-path to add $q^\ell$ paths of length $\ell$.

Choose $p, q, k, \ell$ so that the number of added paths is much larger than $n!$, so that the added paths determine (up to lower-order terms) the average path length. Choose $k$ and $\ell$ with $k < n-1 \ll \ell$, so that the average path length is larger than $n$, and closer to $n$ than to $\ell$. (Details below.)

Then the typical path will be a Hamiltonian path from $s$ to $t$ in the original graph, if there is one.

Here are the details for choosing $p, q, k, \ell$. Choose $p=n^{30}$, $q=n^2$, $k=n/3$, and $\ell=5n$. Then the addition adds $p^k = n^{10n}$ paths of length $k=n/3$, and $q^\ell = n^{10n}$ paths of length $\ell= 5n$. The average length of the added paths is then $(1/3 + 5)n/2 = 8n/3$. If there is a Hamiltonian $s$-$t$ path in the original graph, its length will be about $5n/3$ shorter than the average. The longer added paths, of length $5n$, are about $7n/3$ longer than the average, so they are not better. (Note that there are at most $n! \ll n^{10n}$ paths in the original graph, of length at most $n$, so they affect the average path length in the final graph by only lower-order terms.)

If a multigraph is not allowed, the construction can be adjusted appropriately by splitting each multi-edge as usual, then taking account how this affects $k$ and $\ell$. $~~~\Box$

$\endgroup$
1
  • $\begingroup$ This can surely be extended to show hardness of approximating even the unweighted case, by reducing from the longest-path problem (which is hard to approximate) instead of from hamiltonian path. $\endgroup$
    – Neal Young
    Oct 22, 2022 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.