<p><strong>Lemma 1.</strong> <em>The weighted problem is NP-hard by reduction from Partition.</em></p>
<p><strong>Lemma 2.</strong> <em>The unweighted problem is NP-hard by reduction from Hamiltonian Path.</em></p>
<p><em>Proof of Lemma 1.</em> Given a Partition instance <span class="math-container">$(x_1, \ldots, x_n)$</span>, construct the multigraph <span class="math-container">$G=(V,E)$</span> with <span class="math-container">$V=[n+1]$</span> and, for each <span class="math-container">$i\in [n]$</span>, two copies of edge <span class="math-container">$(i, i+1)$</span>, one with weight <span class="math-container">$x_i$</span> and the other with weight zero.  Then ask for the path from <span class="math-container">$1$</span> to <span class="math-container">$n+1$</span> whose weight is as close to average over paths from <span class="math-container">$1$</span> to <span class="math-container">$n+1$</span>.</p>
<p>By linearity of expectation, the average weight is <span class="math-container">$\sum_{i=1}^n x_i/2$</span>, so there is a path with average weight if and only if the Partition instance is feasible.</p>
<p>(If desired, the multigraph can easily be converted to an equivalent graph by splitting each edge <span class="math-container">$(i, i+1)$</span> of weight zero into two zero-weight edges.) <span class="math-container">$~~~\Box$</span></p>
<p><em>Proof sketch for Lemma 2.</em>  Given a Hamiltonian Path instance <span class="math-container">$G=(V,E)$</span> with source <span class="math-container">$s$</span> and sink <span class="math-container">$t$</span>, construct the following multigraph <span class="math-container">$G'$</span>.  Let <span class="math-container">$n=|V|$</span>.</p>
<p>First, add a new, long &quot;super-path&quot; from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> as follows.  Fix some <span class="math-container">$p, q, k, \ell$</span> to be determined later. Add <span class="math-container">$k$</span> new vertices <span class="math-container">$a_1, a_2, \ldots, a_k$</span>, with <span class="math-container">$p$</span> new multi-edges <span class="math-container">$(a_i, a_{i+1})$</span> between each consecutive pair.  Add edges <span class="math-container">$(s, a_1)$</span> and <span class="math-container">$(a_k, t)$</span>.  This addition adds <span class="math-container">$p^k$</span> paths of length <span class="math-container">$k$</span> from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>.</p>
<p>Now add another (separate) super-path to add <span class="math-container">$q^\ell$</span> paths of length <span class="math-container">$\ell$</span>.</p>
<p>Choose <span class="math-container">$p, q, k, \ell$</span> so that the number of added paths is much larger than <span class="math-container">$n!$</span>, so that the added paths determine (up to lower-order terms) the average path length.  Choose <span class="math-container">$k$</span> and <span class="math-container">$\ell$</span> with <span class="math-container">$k &lt; n-1 \ll \ell$</span>, so that the average path length is larger than <span class="math-container">$n$</span>, and closer to <span class="math-container">$n$</span> than to <span class="math-container">$\ell$</span>.  (Details below.)</p>
<p>Then the typical path will be a Hamiltonian path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> in the original graph, if there is one.</p>
<p>Here are the details for choosing <span class="math-container">$p, q, k, \ell$</span>.
Choose <span class="math-container">$p=n^{30}$</span>, <span class="math-container">$q=n^2$</span>, <span class="math-container">$k=n/3$</span>, and <span class="math-container">$\ell=5n$</span>.
Then the addition adds
<span class="math-container">$p^k = n^{10n}$</span> paths of length <span class="math-container">$k=n/3$</span>,
and
<span class="math-container">$q^\ell = n^{10n}$</span> paths of length <span class="math-container">$\ell= 5n$</span>.
The average length of the added paths is then <span class="math-container">$(1/3 + 5)n/2 = 8n/3$</span>.
If there is a Hamiltonian <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path in the original graph, its length will be about <span class="math-container">$5n/3$</span> shorter than the average.
The longer added paths, of length <span class="math-container">$5n$</span>, are about <span class="math-container">$7n/3$</span> longer than the average, so they are not better.
(Note that there are at most <span class="math-container">$n! \ll n^{10n}$</span> paths in the original graph, of length at most <span class="math-container">$n$</span>, so they affect the average path length in the final graph by only lower-order terms.)</p>
<p>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 <span class="math-container">$k$</span> and <span class="math-container">$\ell$</span>. <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2022-10-22T19:31:02.420Z
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.
Neal Young
CC BY-SA 4.0
2022-10-22T10:58:11.043Z
2022-10-22T15:08:39.350Z
2022-10-22T15:08:39.350Z
Neal Young
<p>Consider an undirected graph with two distinguished nodes <span class="math-container">$u\neq v$</span>. How hard is it to find an <span class="math-container">$u-v$</span> path, such that its length is as close to the average <span class="math-container">$u-v$</span> path length as possible?</p>
<p>Formally, for a path <span class="math-container">$P$</span> let <span class="math-container">$\ell(P)$</span> denote its length (number of edges on <span class="math-container">$P$</span>, but a weighted version may also be considered). Let <span class="math-container">$A$</span> denote the average length of simple <span class="math-container">$u-v$</span> paths:
<span class="math-container">$$A= \frac{1}{N}\sum \ell(P)$$</span>
where <span class="math-container">$N$</span> is the number of simple <span class="math-container">$u-v$</span> paths and the summation is taken over all such paths.
Let us call a simple <span class="math-container">$u-v$</span> path <span class="math-container">$P_0$</span> <em>typical</em> if <span class="math-container">$|\ell(P_0)-A|$</span> is minimum.</p>
<p><strong>Question:</strong> What is the complexity of finding such a typical path? Is anything known about this problem?</p>

CC BY-SA 4.0
2022-10-22T10:59:04.207Z
Does anybody know the complexity of *sampling* a simple $u$-$v$ path uniformly at random?  That could be useful for approximating the unweighted case.
Neal Young
<graph-theory><graph-algorithms><np-hardness><polynomial-time>
Finding a "typical" path
Andras Farago
# Finding a "typical" path

(Asked by: username_0 on 2022-10-22)

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?

**Tags:** graph-theory, graph-algorithms, np-hardness, polynomial-time
> **Comments:**
> **username_1**: Does anybody know the complexity of *sampling* a simple $u$-$v$ path uniformly at random?  That could be useful for approximating the unweighted case.  

---

## 1 answers

### Answer by username_1 on 2022-10-22. Score: 2 | Accepted answer

**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$

> **Comments:**
> **username_1**: 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.  

---

