Timeline for Minimum separating subdivision in Plane
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 19, 2011 at 20:51 | vote | accept | user695652 | ||
| Dec 19, 2011 at 18:33 | comment | added | Igor Rivin | @Ori: Oh, OK, that's what one gets for skimming... | |
| Dec 19, 2011 at 16:49 | comment | added | Ori Gurel-Gurevich | I did write "(a version of) minimum $k$-cut". If you look at wikipedia it explicitly mention this version: "It is also NP-complete if we specify k vertices and ask for the minimum k-cut which separates these vertices among each of the sets". Also, the paper I linked deals with this version: "a multiway cut (also called a multi-terminal cut) problem asks for a subset of edges with minimum total length and whose removal disconnects each terminal from the others". | |
| Dec 19, 2011 at 16:21 | comment | added | Igor Rivin | @Louis+@Joe: I don't see how this is equivalent (since we have the $k$ marked vertices, we don't have the choice of what the connected components are, which should make the problem easier. | |
| Dec 19, 2011 at 15:11 | comment | added | Joseph O'Rourke | @Louis: Thanks! What I didn't see is the marking, but now I understand that also separating marked vertices falls under the same umbrella as just separating into $k$ components. | |
| Dec 19, 2011 at 14:56 | comment | added | Louis | @Joe: Here is a dual version of the question: we are given a planar graph with $k$ marked vertices and we want a minimum-sized set of edges that, when removed, disconnects the marked vertices from each other. I think this is what Ori had in mind. | |
| Dec 19, 2011 at 14:26 | comment | added | Joseph O'Rourke | @Ori: Could you please sketch the equivalence of the stated problem to min $k$-cut? I don't doubt you, but it is not obvious to me. Thanks. | |
| Dec 19, 2011 at 7:44 | history | answered | Ori Gurel-Gurevich | CC BY-SA 3.0 |