# Finding a "typical" path

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?

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

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

• 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. Oct 22, 2022 at 19:31