Let $T=(\mathcal{V},\mathcal{E})$ be an udirected acyclic graph and $|\mathcal{V}|=n$. Let $\mathcal{V'}$ be $\mathcal{V'}\subset \mathcal{V}$ where $|\mathcal{V'}|=2m\leq n$. There are $2m \choose 2$ pairs of nodes in the set $\mathcal{V'}$. For each pair of nodes $(w,w')$ in the set $\mathcal{V'}$, there is a unique path form $w$ to $w'$ lets call it $\text{path}(w,w')$ and it contains all the edges in the path of $w,w'$. I would like to find a collection of pairs of nodes of $\mathcal{V'}$, where each node of $\mathcal{V'}$ appears in one pair exactly, thus we have $m$ pairs in total in the final desired collection. Lets call that collection of pairs $F(\mathcal{V'})$, also, $F(\mathcal{V'})$ should be found such that the total number of edges in the paths $\text{path}(w,w')$ is minimum, where $(w,w')\in F(\mathcal{V'}):$$$\min_{F(\mathcal{V'})} \sum_{(w,w')\in F(\mathcal{V'})} |\text{path}(w,w')|. $$ Notice that a necessary condition for the choice of pairs $F(\mathcal{V'})$ is that the paths should be disjointed (have no common edges), otherwise we have a total number of edges greater than the minimum possible.

I would like to know what the algorithm is that finds $F(\mathcal{V'})$ in polynomial time. Is this related to the Hamiltonian cycle problem? My graph is acyclic which should help to get a polynomial time algorithm. *By disjointed paths I mean paths with no common edges, they may have common vertices. **By minimum path cover I mean the total number of edges in the collection of paths is minimum since the number of paths is always chosen to be $m$.


A Trivial Algorithm

You can compute the lengths of all-pair shortest paths among $\mathcal{V}'$, and solve a minimum perfect matching in a complete graph on $\mathcal{V}'$ where the weight of an edge $(u,v)$ is the length of the shortest path from $u$ to $v$.

A Smarter Algorithm

Consider the connected component containing $\mathcal{V}'$, it must be a tree.

At each step we move the deepest nodes in $\mathcal{V}'$ to their fathers. If two nodes move to the same node, we decide to match them and do not consider them any more in following steps. If more than two nodes move to the same node, repeatedly match arbitrary two of them until no more than one node is left.

This algorithm runs in $O(|\mathcal{E}|)$.

  • $\begingroup$ I don't get what you're trying to say in your 2nd paragraph: If the graph can be reduced to a single spanning tree then it must be connected, and since we know it's undirected and acyclic, it must be already be a (spanning) tree. Otherwise good! $\endgroup$ – j_random_hacker Apr 3 '18 at 12:35
  • $\begingroup$ @j_random_hacker You are right, I forgot the fact that a connected acyclic graph is a tree. $\endgroup$ – xskxzr Apr 3 '18 at 12:55
  • $\begingroup$ I understood that the spanning tree is not necessary but I thought that you were trying to solve a more general problem, for instance, assume a graph instead of a tree such that for the nodes in $\mathcal{V'}$ is only guaranteed that there is a unique path. $\endgroup$ – Cauchy Apr 3 '18 at 18:00
  • $\begingroup$ I have one question: when you move a node to its ancestor don't you have to search if any other node was moved to that previously? Is this going to increase the complexity? $\endgroup$ – Cauchy Apr 4 '18 at 2:29
  • $\begingroup$ @Cauchy You can store in the ancestor which node is in this ancestor now. Since each time two nodes meet we can match them immediately, there is at most one node stored. Also note each step you move the deepest nodes, so nodes would not leave this ancestor before (including) this step. $\endgroup$ – xskxzr Apr 4 '18 at 2:39

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.