Return to Answer

Let $G = (V, E)$ be a digraph. We define a "rho of length $k$" as a finite sequence of $k$ vertices, each a neighbor of its predecessor, where exactly one of the following two conditions hold

1. All $k$ vertices are distinct, and the last vertex has no neighbors.
2. The first $k-1$ vertices of the sequence are distinct, and the last vertex is one of the first $k-1$ members of the sequence.

Let $R(G)$ be the set of all rhos contained in $G$. Given $\rho \in R(G)$ by abuse of notation define $E(\rho)$ to be the edges of $\rho$. Extending the notation $R$, let $R(G; v)$ be the set of all rhos in $G$ whose initial vertex is $v$. We describe the "Rho Cover Problem" for a graph $G$ and vertex $v$ as the problem of finding the smallest set of rhos which start at $v$ and cover the edges of $G$.

Mathematically speaking, we can exhaustively check all subsets of $\{E(\rho) : \rho \in R(G; v)\}$, note the ones which cover $E$, and return one of minimal cardinality. The conditions to show such a subset exists were addressed David Eppstein: for all edges $(w,z)$ in $G$ there must be a path from $v$ to $w$.

From a computer science perspective you can now ask if there is an "easy" solution. My expectation is that answering this question would involve either finding a polynomial time algorithm for this problem (in which case it would be "easy") or showing the problem is NP-complete (in which case it would be "hard"). This would be best answered in either cs or cstheory depending on the caliber of the question (which I cannot judge).

From a programming perspective, you seem to be asking for a practical way to solve this problem for graphs with approximately 10 vertices. With so few vertices you can enumerate every rho v̶i̶a̶ ̶a̶ ̶d̶e̶p̶t̶h̶ ̶f̶i̶r̶s̶t̶ ̶s̶e̶a̶r̶c̶h̶ and consider the Rho Cover Problem as a special instance of the Set Cover Problem. As noted in the Wikipedia article on the Set Cover Problem this can be expressed as an Integer Linear Programming Problem. To solve such a problem I would recommend an academic licence of Gurobi. I have found it to be an extremely powerful piece of software designed first and foremost for optimization.

Best of luck.

Let $G = (V, E)$ be a digraph. We define a "rho of length $k$" as a finite sequence of $k$ vertices, each a neighbor of its predecessor, where exactly one of the following two conditions hold

1. All $k$ vertices are distinct, and the last vertex has no neighbors.
2. The first $k-1$ vertices of the sequence are distinct, and the last vertex is one of the first $k-1$ members of the sequence.

Let $R(G)$ be the set of all rhos contained in $G$. Given $\rho \in R(G)$ by abuse of notation define $E(\rho)$ to be the edges of $\rho$. Extending the notation $R$, let $R(G; v)$ be the set of all rhos in $G$ whose initial vertex is $v$. We describe the "Rho Cover Problem" for a graph $G$ and vertex $v$ as the problem of finding the smallest set of rhos which start at $v$ and cover the edges of $G$.

Mathematically speaking, we can exhaustively check all subsets of $\{E(\rho) : \rho \in R(G; v)\}$, note the ones which cover $E$, and return one of minimal cardinality. The conditions to show such a subset exists were addressed David Eppstein: for all edges $(w,z)$ in $G$ there must be a path from $v$ to $w$.

From a computer science perspective you can now ask if there is an "easy" solution. My expectation is that answering this question would involve either finding a polynomial time algorithm for this problem (in which case it would be "easy") or showing the problem is NP-complete (in which case it would be "hard"). This would be best answered in either cs or cstheory depending on the caliber of the question (which I cannot judge).

From a programming perspective, you seem to be asking for a practical way to solve this problem for graphs with approximately 10 vertices. With so few vertices you can enumerate every rho v̶i̶a̶ ̶a̶ ̶d̶e̶p̶t̶h̶ ̶f̶i̶r̶s̶t̶ ̶s̶e̶a̶r̶c̶h̶ and consider the Rho Cover Problem as a special instance of the Set Cover Problem. As noted in the Wikipedia article on the Set Cover Problem this can be expressed as an Integer Linear Programming Problem. To solve such a problem I would recommend an academic licence of Gurobi. I have found it to be an extremely powerful piece of software designed first and foremost for optimization.

Best of luck.

Let $G = (V, E)$ be a digraph. We define a "rho of length $k$" as a finite sequence of $k$ vertices, each a neighbor of its predecessor, where exactly one of the following two conditions hold

1. All $k$ vertices are distinct, and the last vertex has no neighbors.
2. The first $k-1$ vertices of the sequence are distinct, and the last vertex is one of the first $k-1$ members of the sequence.

Let $R(G)$ be the set of all rhos contained in $G$. Given $\rho \in R(G)$ by abuse of notation define $E(\rho)$ to be the edges of $\rho$. Extending the notation $R$, let $R(G; v)$ be the set of all rhos in $G$ whose initial vertex is $v$. We describe the "Rho Cover Problem" for a graph $G$ and vertex $v$ as the problem of finding the smallest set of rhos which start at $v$ and cover the edges of $G$.

Mathematically speaking, we can exhaustively check all subsets of $\{E(\rho) : \rho \in R(G; v)\}$, note the ones which cover $E$, and return one of minimal cardinality. The conditions to show such a subset exists were addressed David Eppstein: for all edges $(w,z)$ in $G$ there must be a path from $v$ to $w$.

From a computer science perspective you can now ask if there is an "easy" solution. My expectation is that answering this question would involve either finding a polynomial time algorithm for this problem (in which case it would be "easy") or showing the problem is NP-complete (in which case it would be "hard"). This would be best answered in either cs or cstheory depending on the caliber of the question (which I cannot judge).

From a programming perspective, you seem to be asking for a practical way to solve this problem for graphs with approximately 10 vertices. With so few vertices you can enumerate every rho v̶i̶a̶ ̶a̶ ̶d̶e̶p̶t̶h̶ ̶f̶i̶r̶s̶t̶ ̶s̶e̶a̶r̶c̶h̶ and consider the Rho Cover Problem as a special instance of the Set Cover Problem. As noted in the Wikipedia article on the Set Cover Problem this can be expressed as an Integer Linear Programming Problem. To solve such a problem I would recommend an academic licence of Gurobi. I have found it to be an extremely powerful piece of software designed first and foremost for optimization.

Best of luck.

Let $G = (V, E)$ be a digraph. We define a "rho of length $k$" as a finite sequence of $k$ vertices, each a neighbor of its predecessor, where exactly one of the following two conditions hold

1. All $k$ vertices are distinct, and the last vertex has no neighbors.
2. The first $k-1$ vertices of the sequence are distinct, and the last vertex is one of the first $k-1$ members of the sequence.

Let $R(G)$ be the set of all rhos contained in $G$. Given $\rho \in R(G)$ by abuse of notation define $E(\rho)$ to be the edges of $\rho$. Extending the notation $R$, let $R(G; v)$ be the set of all rhos in $G$ whose initial vertex is $v$. We describe the "Rho Cover Problem" for a graph $G$ and vertex $v$ as the problem of finding the smallest set of rhos which start at $v$ and cover the edges of $G$.

Mathematically speaking, we can exhaustively check all subsets of $\{E(\rho) : \rho \in R(G; v)\}$, note the ones which cover $E$, and return one of minimal cardinality. The conditions to show such a subset exists were addressed David Eppstein: for all edges $(w,z)$ in $G$ there must be a path from $v$ to $w$.

From a computer science perspective you can now ask if there is an "easy" solution. My expectation is that answering this question would involve either finding a polynomial time algorithm for this problem (in which case it would be "easy") or showing the problem is NP-complete (in which case it would be "hard"). This would be best answered in either cs or cstheory depending on the caliber of the question (which I cannot judge).

From a programming perspective, you seem to be asking for a practical way to solve this problem for graphs with approximately 10 vertices. With so few vertices you can enumerate every rho v̶i̶a̶ ̶a̶ ̶d̶e̶p̶t̶h̶ ̶f̶i̶r̶s̶t̶ ̶s̶e̶a̶r̶c̶h̶ and consider the Rho Cover Problem as a special instance of the Set Cover Problem. As noted in the Wikipedia article on the Set Cover Problem this can be expressed as an Integer Linear Programming Problem. To solve such a problem I would recommend an academic licence of Gurobi. I have found it to be an extremely powerful piece of software designed first and foremost for optimization.

Best of luck.

Let $G = (V, E)$ be a digraph. We define a "rho of length $k$" as a finite sequence of $k$ vertices, each a neighbor of its predecessor, where exactly one of the following two conditions hold

1. All $k$ vertices are distinct, and the last vertex has no neighbors.
2. The first $k-1$ vertices of the sequence are distinct, and the last vertex is one of the first $k-1$ members of the sequence.

Let $R(G)$ be the set of all rhos contained in $G$. Given $\rho \in R(G)$ by abuse of notation define $E(\rho)$ to be the edges of $\rho$. Extending the notation $R$, let $R(G; v)$ be the set of all rhos in $G$ whose initial vertex is $v$. We describe the "Rho Cover Problem" for a graph $G$ and vertex $v$ as the problem of finding the smallest set of rhos which start at $v$ and cover the edges of $G$.

Mathematically speaking, we can exhaustively check all subsets of $\{E(\rho) : \rho \in R(G; v)\}$, note the ones which cover $E$, and return one of minimal cardinality. The conditions to show such a subset exists were addressed David Eppstein: for all edges $(w,z)$ in $G$ there must be a path from $v$ to $w$.

From a computer science perspective you can now ask if there is an "easy" solution. My expectation is that answering this question would involve either finding a polynomial time algorithm for this problem (in which case it would be "easy") or showing the problem is NP-complete (in which case it would be "hard"). This would be best answered in either cs or cstheory depending on the caliber of the question (which I cannot judge).

From a programming perspective, you seem to be asking for a practical way to solve this problem for graphs with approximately 10 vertices. With so few vertices you can enumerate every rho (via a depth first search) and consider the Rho Cover Problem as a special instance of the Set Cover Problem. As noted in the Wikipedia article on the Set Cover Problem this can be expressed as an Integer Linear Programming Problem. To solve such a problem I would recommend an academic licence of Gurobi. I have found it to be an extremely powerful piece of software designed first and foremost for optimization.

Best of luck.

Let $G = (V, E)$ be a digraph. We define a "rho of length $k$" as a finite sequence of $k$ vertices, each a neighbor of its predecessor, where exactly one of the following two conditions hold

1. All $k$ vertices are distinct, and the last vertex has no neighbors.
2. The first $k-1$ vertices of the sequence are distinct, and the last vertex is one of the first $k-1$ members of the sequence.

Let $R(G)$ be the set of all rhos contained in $G$. Given $\rho \in R(G)$ by abuse of notation define $E(\rho)$ to be the edges of $\rho$. Extending the notation $R$, let $R(G; v)$ be the set of all rhos in $G$ whose initial vertex is $v$. We describe the "Rho Cover Problem" for a graph $G$ and vertex $v$ as the problem of finding the smallest set of rhos which start at $v$ and cover the edges of $G$.

Mathematically speaking, we can exhaustively check all subsets of $\{E(\rho) : \rho \in R(G; v)\}$, note the ones which cover $E$, and return one of minimal cardinality. The conditions to show such a subset exists were addressed David Eppstein: for all edges $(w,z)$ in $G$ there must be a path from $v$ to $w$.

From a computer science perspective you can now ask if there is an "easy" solution. My expectation is that answering this question would involve either finding a polynomial time algorithm for this problem (in which case it would be "easy") or showing the problem is NP-complete (in which case it would be "hard"). This would be best answered in either cs or cstheory depending on the caliber of the question (which I cannot judge).

From a programming perspective, you seem to be asking for a practical way to solve this problem for graphs with approximately 10 vertices. With so few vertices you can enumerate every rho v̶i̶a̶ ̶a̶ ̶d̶e̶p̶t̶h̶ ̶f̶i̶r̶s̶t̶ ̶s̶e̶a̶r̶c̶h̶ and consider the Rho Cover Problem as a special instance of the Set Cover Problem. As noted in the Wikipedia article on the Set Cover Problem this can be expressed as an Integer Linear Programming Problem. To solve such a problem I would recommend an academic licence of Gurobi. I have found it to be an extremely powerful piece of software designed first and foremost for optimization.

Best of luck.