Timeline for Strategic vertex labeling
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13, 2013 at 3:03 | comment | added | 372 | @David Benson-Putnins, I mentioned the boundary as an illustration. Obviously the 0s inside the $G'$ need to be considered as well. | |
| May 13, 2013 at 2:42 | comment | added | David Benson-Putnins | Actually wait this makes the problem fairly trivial "the challenge is to relabel the 0s on the side of G′ in such way that product of labels on both sides maximizes the sum " If all I'm worried about is the sum over the boundary edges then I can pick each vertex independently as a 1 or a -1 to maximize the sum of its edge weights. It's only interesting if the internal edges of G' are included as well | |
| May 13, 2013 at 2:08 | history | edited | Dustin G. Mixon | CC BY-SA 3.0 |
added 148 characters in body
|
| May 13, 2013 at 2:06 | comment | added | Dustin G. Mixon | Ah - good point. I failed to notice that the edge weights are all positive! | |
| May 13, 2013 at 1:49 | comment | added | David Benson-Putnins | Dustin, I don't think it's correct anyway. The correct labeling of G' would be to just set every value to 1. Solving maxcut would be equivalent to minimizing the sum wouldn't it? | |
| May 12, 2013 at 20:01 | comment | added | 372 | @Dustin G. Mixon, you are right, the problem did not say it clearly that $G'$ has all 0 and my previous comment is wrong. $G-G'$ contains only {1,-1}. | |
| May 12, 2013 at 18:54 | comment | added | Dustin G. Mixon | @Joseph: You should edit your question then. Make it clear that $G'$ is a subset of the $0$-vertices, and that the sum is not over all edges, but rather over the boundary of $G'$. Note that if the sum were over all edges, then my answer would be correct. | |
| May 12, 2013 at 18:40 | comment | added | 372 | @David Benson-Putnins, My apologies for possible misrepresentation. Set $G'$ indeed contains only vertices with values 0, however, intuitively speaking, the vertices that are close to the boundary have edges that reach out to the $G-G'$ where vertices can have labels from {0,-1,1}. So yes, vertices in $G-G'$ can have any value(either 0, 1 or -1) | |
| May 12, 2013 at 18:29 | comment | added | David Benson-Putnins | Joseph this comment confused me a little.. from your original post I would have thought that G' had ALL the vertices with weight 0, but from the comment it sounds like G' only contains some of them, and some might be left in G. I'm not sure if it makes a difference in the problem since any leftover 0 vertices can just be ignored but I wanted to check which interpretation is correct | |
| May 12, 2013 at 18:12 | comment | added | 372 | @Dustin G. Mixon, thank you for your input. Although on the surface the max-cut seems to be similar, in reality the problems are quite different. The challenge in the problem I posted is to chose values of nodes on any given edge such that the product of such values $l_u l_v$ stays non-negative. Since we have boundary between $G$ and $G'$ such that edges intersected by the boundary on the side of $G'$ have nodes with values 0 and on the side of $G$ with have values{0,-1,1} the challenge is to relabel the 0s on the side of $G'$ in such way that product of labels on both sides maximizes the sum | |
| May 12, 2013 at 17:21 | history | answered | Dustin G. Mixon | CC BY-SA 3.0 |