4
$\begingroup$

Suppose we have a path on $N$ nodes ($N$ is even). We want to connect them with new $\frac N2$ vertex-disjoint edges (i.e. perfect matching) such that largest distance between any two nodes is minimized (the distance between two nodes is the length of the shortest path).

One way is a greedy method of finding the shortest distances between all pairs and adding a new edge between two nodes with the largest distance. We repeat until $\frac N2$ edges (perfect matching) are added.

What is the largest distance between any two nodes (the diameter)? Is there a better method to minimize the diameter?

$\endgroup$
  • 1
    $\begingroup$ The way you describe gets you to a blind alley when the only two vertices are left are already adjacent. Let $N = 6$ and you have path $v_1, v_2, \ldots, v_6$. Firstly you connect $v_1$ and $v_6$, then $v_2$ and $v_5$ and don't know what to do with $v_3$ and $v_4$. Also distance between $v_1$ and $v_4$ remains $3$, while other set of new edges gives diameter $2$: $v_1v_6$, $v_2v_4$ and $v_3v_5$. $\endgroup$ – Smylic Apr 5 '17 at 9:15
  • 1
    $\begingroup$ Aha, Do you have a better method? $\endgroup$ – Mohammad Al-Turkistany Apr 5 '17 at 9:18
2
$\begingroup$

I suspect that the minimum diameter is $d = \lfloor \log_2 N \rfloor$. I've tested this by brute force for $N \le 16$, and I also have:

  • A proof that $d \ge \lfloor \log_2 N \rfloor$.
  • A method for adding a matching that achieves $d \le 2 \lfloor \log_2 N \rfloor$.

For the proof: if you start from one endpoint of the path and explore the augmented graph via breadth-first search, then you have $2$ choices for the first step (follow the path, or take the edge from the matching) and at most $2$ choices for every step thereafter (each vertex has degree at most $3$, and one of the edges is the edge we took to enter it. So for each $k \ge 0$, there are at most $2^k$ vertices in the $k^{\text{th}}$ level of the breadth-first search tree. This gives us at most $2^{k+1} - 1$ vertices within the first $k$ levels, and if the graph has diameter $d$, we know that $N \le 2^{d+1} - 1$. This gives a lower bound of $d \ge \lfloor \log_2 N \rfloor$.

In the hope that this will be tight, we can construct a breadth-first search tree in which none of the vertices overlap. Example for $3$ levels:

unfinished graph

This gives a graph with $2^{d+1}-1$ vertices, which is at least one vertex more than we want, possibly more. So we can delete one or more vertices and join the remaining vertices arbitrarily. In the example, we can take the following graph:

finished N=14 graph

This will not necessarily have diameter $\lfloor \log_2 N \rfloor$, but it guarantees that every vertex is within $\lfloor \log_2 N \rfloor$ steps of the leftmost vertex. So to get from any vertex to any other, we can find paths of length $\lfloor \log_2 N \rfloor$ from each that meet at the leftmost vertex, for a path that has total length $2\lfloor \log_2 N \rfloor$.

We can probably do better by a clever choice of the remaining matching edges (as well as a clever choice of how to fit together the disconnected parts of the path.)

$\endgroup$
  • $\begingroup$ To be more precise $N \le 2^{d + 1} - 1$ implies $d \ge \lfloor \log_2 (N + 1)\rfloor - 1$ that is not so strong bound as $d \ge \lfloor \log_2 N \rfloor$. Also why do you subtract $1$ from total length of a path after multiplying radius by $2$? Anyway that's a good result. $\endgroup$ – Smylic Apr 6 '17 at 13:09
  • $\begingroup$ I think I'm good with the floor: e.g., $d=5 \implies N \le 63 \implies \log_2 N < 6 \implies \lfloor \log_2 N \rfloor \le 5$. I shouldn't be subtracting $1$, though, I'll fix that. $\endgroup$ – Misha Lavrov Apr 6 '17 at 13:51
  • $\begingroup$ Yes, my bad: $N \le 2^{d + 1} - 1$ in truth implies $d \ge \log_2 (N + 1) - 1$ therefore $d \ge \lceil \log_2 (N + 1) \rceil - 1 = \lfloor \log_2 N \rfloor$. $\endgroup$ – Smylic Apr 6 '17 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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