<p>What is $f$? I seems that you're asking for a one-to-one mapping between a power set over a power set of edges and the edges - which would surely be possible only if there's no more than one edge.</p>

CC BY-SA 2.5
2011-01-11T08:10:57.220Z
The color also contributes to the mapping. The purpose is to find a the $P_s$ with minimum size such that f exists. If more paths are chosen, no f exists; if too less paths are chosen, no f exists.
Jing
CC BY-SA 2.5
2011-01-11T09:29:09.423Z
Let me restate my question: what is the domain of $f$? The range and the co-domain are clearly both $E$, but the domain appears to be $\{red,blue\} \cup \{red,blue\}\times\{red,blue\} \cup \{red,blue\}\times\{red,blue\}\times\{red,blue\} \cup \ldots$ until the final element in the union is a Cartesian product of $|P_s|$ copies of {red,blue}.
Peter Taylor
CC BY-SA 2.5
2011-01-11T17:57:13.717Z
Peter, now that you have enough rep, this answer should really have been a comment.
Suresh Venkat
CC BY-SA 2.5
2011-01-11T18:29:00.403Z
I didn't have enough rep when I made it.
Peter Taylor
CC BY-SA 2.5
2011-01-12T03:21:48.027Z
To Peter, thanks for help. I give an example. Given a graph $G$ with $E=\{e_1,e_2,e_3,e_4\}$, and there are three paths $P_1=\{e_1,e_2\}$ and $P_2=\{e_2,e_3\}$ and $P_3=\{e_3, e_4\}$. If $e_1$ is colored by red, then only $P_1$ is red;if only $e_2$ is colored by red, then only $P_1,P_2$ are red; if only $e_3$ is colored by red, then only $P_2, P_3$ are red; if only $e_4$ is colored by red, then $P_3$ is red. $f(P_1^r,P_2^b,P_3^b,P_4^b)=e_1$; $f(P_1^r,P_2^r,P_3^b,P_4^b)=e_2$; $f(P_1^b,P_2^r,P_3^r,P_4^b)=e_3$; $f(P_1^b,P_2^b,P_3^b,P_4^r)=e_4$.This example shows the domain of f.
Jing
CC BY-SA 2.5
2011-01-12T03:23:15.920Z
($P_1^b$ means path $P_1$ is colored by blue; $P_1^r$ means path $P_1$ is colored by red)
Jing
CC BY-SA 2.5
2011-01-12T07:32:29.077Z
I finally think I get where you're going, but I don't think the way you describe $f$ is correct. $f^{-1}$ is an injective function from $E$ to the power set of $P_s$. And with a bit of work it can be defined, but I need to run to catch a bus.
Peter Taylor
CC BY-SA 2.5
2011-01-12T08:03:26.710Z
Is this an accurate restatement of the problem?
Peter Taylor
CC BY-SA 2.5
2011-01-12T08:09:04.723Z
Given a graph $G = (V, E)$ and a path set $P = \{P_1, \ldots, P_m\}$ where $P_i$ is a path between two points in $V$, define $C(e) = \{P_i \in P | e \in P_i\}$ as the paths containing $e$. Define a distinguishing path set as a set $P_s \subseteq P$ such that $(C(e_1) \cap P_s) = (C(e_2) \cap P_s) \Rightarrow e_1 = e_2$. Find a minimal distinguishing path set.
Peter Taylor
CC BY-SA 2.5
2011-01-12T18:07:44.040Z
This can be reformulated as a minimum set cover problem. Consider the set $F = \{\{e_1, e_2\} : e_1 \neq e_2\}$. For each $P_i$ define $S_i = \{\{e_1, e_2\} : (e_1 \in P_i) \neq (e_2 \in P_i)\}$. A cover of $F$ using $S_i$ corresponds to a distinguishing path set, and a minimal cover of $F$ using $S_i$ corresponds to a minimal distinguishing path set.
Peter Taylor
CC BY-SA 2.5
2011-01-13T04:26:13.903Z
To Peter, thanks. $f^{-1}$ is indeed an injective function. If we remove the color stuff, your reformulation catches the problem exactly. The simplified version is an NP-hard problem. I will ask my friend for the original paper about the application of such a problem.
Jing
CC BY-SA 2.5
2011-01-11T07:29:33.880Z
2011-01-11T07:29:33.880Z
Peter Taylor
<p>Yesterday, I discussed with one of my EE friends. She asked me an interesting problem and I simplify it by ignoring the bandwidth cost and model as following:
Given a graph $G=(V,E)$ with its path set $P=\{P_1,P_2,\ldots, P_m\}$ where $P_i$ is a path 
between two points in $V$. A path $P_i$ is colored by red if only and only if one of it's edges is colored by red, i.e. $P^c=red$; otherwise $P_i$ is colored by blue, i.e. $P^c=blue$. Find a subset $P_s\subseteq P$ s.t. 1) If for every $j$ color all edges in $G$ by blue except only one $e_j\in E$ by red, 
there is a subset $P_s&#39; =\{P_1,P_2,\ldots,P_t\}$ in $P_s$ such that $f(P_1^c,\ldots,P_t^c)=e_j$ where f() is one-to-one mapping; 2) minimize the size of the result set $P_s$.</p>

<p>My questions are:
1) is there any similar work done in TCS?
2) is there any similar work done in graph theory?
3)2) is there any similar work done in networks?
3) any discussions about this problem are welcome.</p>

CC BY-SA 2.5
2011-01-11T05:58:47.263Z
this question doesn't make a lot of sense in its current form. 1) What does "for every i" refer to, since the subscript of the edge is 'j' 2) what does it mean to have a subset of "different colored paths" 3) what does it mean for these to be "one-to-one" mapped to e_j 4) The title needs to be a lot more descriptive.
Suresh Venkat
CC BY-SA 2.5
2011-01-11T06:23:20.073Z
Thanks, I modify it accordingly. Hope this time it is clear.
Jing
CC BY-SA 2.5
2011-01-11T07:46:59.153Z
still doesn't make sense. what does it mean to "color the edges of G for each j" ? do you have multiple colorings of the graph ? if not, then what does this even mean ?
Suresh Venkat
CC BY-SA 2.5
2011-01-11T07:57:36.457Z
yes, it means multiple colorings. I just want to model the problem in general. I forgot to mention this point. Thanks.
Jing
<ds.algorithms><graph-theory><graph-algorithms>
Is any related work to this m-trails problem ?
Jing
# Is any related work to this m-trails problem ?

(Asked by: username_0 on 2011-01-11)

Yesterday, I discussed with one of my EE friends. She asked me an interesting problem and I simplify it by ignoring the bandwidth cost and model as following:
Given a graph $G=(V,E)$ with its path set $P=\{P\_1,P\_2,\ldots, P\_m\}$ where $P\_i$ is a path
between two points in $V$. A path $P\_i$ is colored by red if only and only if one of it's edges is colored by red, i.e. $P^c=red$; otherwise $P\_i$ is colored by blue, i.e. $P^c=blue$. Find a subset $P\_s\subseteq P$ s.t. 1) If for every $j$ color all edges in $G$ by blue except only one $e\_j\in E$ by red,
there is a subset $P\_s' =\{P\_1,P\_2,\ldots,P\_t\}$ in $P\_s$ such that $f(P\_1^c,\ldots,P\_t^c)=e\_j$ where f() is one-to-one mapping; 2) minimize the size of the result set $P\_s$.

My questions are:
1) is there any similar work done in TCS?
2) is there any similar work done in graph theory?
3)2) is there any similar work done in networks?
3) any discussions about this problem are welcome.

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: this question doesn't make a lot of sense in its current form. 1) What does "for every i" refer to, since the subscript of the edge is 'j' 2) what does it mean to have a subset of "different colored paths" 3) what does it mean for these to be "one-to-one" mapped to e_j 4) The title needs to be a lot more descriptive.  
> **username_0**: Thanks, I modify it accordingly. Hope this time it is clear.  
> **username_1**: still doesn't make sense. what does it mean to "color the edges of G for each j" ? do you have multiple colorings of the graph ? if not, then what does this even mean ?  
> **username_0**: yes, it means multiple colorings. I just want to model the problem in general. I forgot to mention this point. Thanks.  

---

## 1 answers

### Answer by username_2 on 2011-01-11. Score: 2

What is $f$? I seems that you're asking for a one-to-one mapping between a power set over a power set of edges and the edges - which would surely be possible only if there's no more than one edge.

> **Comments:**
> **username_0**: The color also contributes to the mapping. The purpose is to find a the $P_s$ with minimum size such that f exists. If more paths are chosen, no f exists; if too less paths are chosen, no f exists.  
> **username_2**: Let me restate my question: what is the domain of $f$? The range and the co-domain are clearly both $E$, but the domain appears to be $\{red,blue\} \cup \{red,blue\}\times\{red,blue\} \cup \{red,blue\}\times\{red,blue\}\times\{red,blue\} \cup \ldots$ until the final element in the union is a Cartesian product of $|P_s|$ copies of {red,blue}.  
> **username_1**: Peter, now that you have enough rep, this answer should really have been a comment.  
> **username_2**: I didn't have enough rep when I made it.  
> **username_0**: To Peter, thanks for help. I give an example. Given a graph $G$ with $E=\{e_1,e_2,e_3,e_4\}$, and there are three paths $P_1=\{e_1,e_2\}$ and $P_2=\{e_2,e_3\}$ and $P_3=\{e_3, e_4\}$. If $e_1$ is colored by red, then only $P_1$ is red;if only $e_2$ is colored by red, then only $P_1,P_2$ are red; if only $e_3$ is colored by red, then only $P_2, P_3$ are red; if only $e_4$ is colored by red, then $P_3$ is red. $f(P_1^r,P_2^b,P_3^b,P_4^b)=e_1$; $f(P_1^r,P_2^r,P_3^b,P_4^b)=e_2$; $f(P_1^b,P_2^r,P_3^r,P_4^b)=e_3$; $f(P_1^b,P_2^b,P_3^b,P_4^r)=e_4$.This example shows the domain of f.  
> **username_0**: ($P_1^b$ means path $P_1$ is colored by blue; $P_1^r$ means path $P_1$ is colored by red)  
> **username_2**: I finally think I get where you're going, but I don't think the way you describe $f$ is correct. $f^{-1}$ is an injective function from $E$ to the power set of $P_s$. And with a bit of work it can be defined, but I need to run to catch a bus.  
> **username_2**: Is this an accurate restatement of the problem?  
> **username_2**: Given a graph $G = (V, E)$ and a path set $P = \{P_1, \ldots, P_m\}$ where $P_i$ is a path between two points in $V$, define $C(e) = \{P_i \in P | e \in P_i\}$ as the paths containing $e$. Define a distinguishing path set as a set $P_s \subseteq P$ such that $(C(e_1) \cap P_s) = (C(e_2) \cap P_s) \Rightarrow e_1 = e_2$. Find a minimal distinguishing path set.  
> **username_2**: This can be reformulated as a minimum set cover problem. Consider the set $F = \{\{e_1, e_2\} : e_1 \neq e_2\}$. For each $P_i$ define $S_i = \{\{e_1, e_2\} : (e_1 \in P_i) \neq (e_2 \in P_i)\}$. A cover of $F$ using $S_i$ corresponds to a distinguishing path set, and a minimal cover of $F$ using $S_i$ corresponds to a minimal distinguishing path set.  
> **username_0**: To Peter, thanks. $f^{-1}$ is indeed an injective function. If we remove the color stuff, your reformulation catches the problem exactly. The simplified version is an NP-hard problem. I will ask my friend for the original paper about the application of such a problem.  

---

