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.

Improve this question
$\endgroup$
4
  • 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, 2011 at 5:58
  • $\begingroup$ Thanks, I modify it accordingly. Hope this time it is clear. $\endgroup$
    – Jing
    Jan 11, 2011 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, 2011 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, 2011 at 7:57

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.