1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Jan 11 '11 at 5:58
  • $\begingroup$ Thanks, I modify it accordingly. Hope this time it is clear. $\endgroup$ – Jing Jan 11 '11 at 6:23
  • 1
    $\begingroup$ 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 ? $\endgroup$ – Suresh Venkat Jan 11 '11 at 7:46
  • $\begingroup$ yes, it means multiple colorings. I just want to model the problem in general. I forgot to mention this point. Thanks. $\endgroup$ – Jing Jan 11 '11 at 7:57
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jing Jan 11 '11 at 8:10
  • 1
    $\begingroup$ 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}. $\endgroup$ – Peter Taylor Jan 11 '11 at 9:29
  • $\begingroup$ Peter, now that you have enough rep, this answer should really have been a comment. $\endgroup$ – Suresh Venkat Jan 11 '11 at 17:57
  • 2
    $\begingroup$ I didn't have enough rep when I made it. $\endgroup$ – Peter Taylor Jan 11 '11 at 18:29
  • $\begingroup$ 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. $\endgroup$ – Jing Jan 12 '11 at 3:21

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.