4
$\begingroup$

Consider a connected undirected graph $G = \langle V, E\rangle$, we say that a subset $C$ of vertices is a Path-Cover if the following holds. For every finite path $p$, it holds that $p$ traverses all the vertices in $C$ iff $p$ traverses all the vertices in $V$. I am interested in finding a Path-Cover of minimal size in polynomial-time, yet all my attempts failed.

I tried a greedy approach where I start with $C = V$, and then I remove a vertex and check whether the graph remains connected. Yet, I'm not sure whether this greedy approach gives a global minimal Path-Cover.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This is only my Intuition on the problem, without any proof or explicit algorithm. This might yield an algorithm that can calculate directly the minimal path covering, or at least you might be able to use it to approximately solve the problem.

To start out, consider the simplest case: a path graph with $n$ nodes. Clearly, you will need only 2 vertices - both endpoints.

Now, lets take a look at a more complicated (and useful) graph: a cycle with $n$ nodes. The smallest path covering must contain all nodes, since otherwise we can easily construct a path that goes through all nodes except one.

The important bit here, is that we can think of a general graph as a "combination" of such cycles and path graphs (any combination of such graphs with one or more nodes in common).

Basically, an idea behind trying to find the smallest path covering is to identify the cycles and paths. Then, start by "marking" each node at those cycles. Then using the "path graphs" try to identify which nodes you don't have to include (for example, think of two cycles connected by a path. Marking any node in one cycle is the same as marking the "endpoint" of the path graph. So the minimal path covering will mark every node that isnt in the path). Always make sure that both graphs at the endpoints of a path graph are "marked" (a graph is marked if any node in it is marked), as well as any graph connected to a node in a cycle is marked.

This is the basic idea of an algorithm to find which nodes we have to include in the minimal path covering. Try to refine this idea a bit more, and it will give a way to calculate or at least approximate the minimal path covering.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Basically, what im saying here is the following: 1) identify the smallest cycles and paths connecting them 2) mark all nodes at the cycles 3) start removing nodes at connections between two sub-graphs, while only remove if removing still allows both sub-graphs to be considered as marked $\endgroup$
    – nir shahar
    Apr 9, 2021 at 15:24
  • $\begingroup$ Thanks for the answer. I actually had this intuition, and did not succeed to get an exact polynomial-time algorithm with it, so I will ponder about it more. $\endgroup$
    – bbb3321
    Apr 9, 2021 at 15:44
  • $\begingroup$ An algorithm can be given by first using DFS to compute the cycles. If a cycle contains another cycle, then split it to two cycles. That is, simply look at the set of all cycles that cannot be split further to two graphs. Then, start by marking every node in the cycles and every endpoint of the path graps. After that, for each node that connects two sub-graphs, try to check whether you can unmark that node or not. The resulting algorithm will be polynomial, but you might even be able to find a faster algorithm that checks the unmarking in some sophisticated way. $\endgroup$
    – nir shahar
    Apr 9, 2021 at 16:06
  • $\begingroup$ I may be wrong, but if you consider a $n$-cycle $(v_1, …, v_n)$, and add a vertex $v$ adjacent only to $v_1$, then $\{v, v_2, v_n\}$ is a path covering that does not contains each vertex of the cycle (and other vertices than the node connecting the cycle to the subgraph $\{v\}$ have been removed). That is, of course, unless you consider non-simple path. $\endgroup$
    – Nathaniel
    Apr 9, 2021 at 16:13
  • $\begingroup$ I agree with you, however I understood the OP wanted a general path, that may be non-simple (since he didn't explicitly state he wanted a simple path). I think its true especially since the graph may not even contain a simple path going trough all vertices. $\endgroup$
    – nir shahar
    Apr 9, 2021 at 16:28

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.