Timeline for NP hard problems on UD graphs
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 3, 2014 at 13:17 | comment | added | Pavan Sangha | Ok this is was what i suspected, i thought that would be the problem but i wanted to double check. Thanks so much for your help! | |
| Dec 2, 2014 at 14:51 | comment | added | Arnaud | I finally think I understand your problem. The difference between both embeddings lies in the parity of the number of intermediate vertices. In Johnson's reduction, it is key that this number is even, otherwise the vertex cover problems are not equivalent. On the other hand, when trying to obtain grid graphs, the bipartite constraint makes it so that this evenness is not possible anymore, as you can see with the triangle graph (0,0), (0,1), (1,0) where the edge (0,1)-(1,0) goes through (1,1): there is no way to scale the grid such that every edge has an even number of intermediate vertices. | |
| Dec 2, 2014 at 11:05 | comment | added | Pavan Sangha | Ok so my next question is naturally, if I take my planar graph where finding a minimum vertex cover is NP-Hard, I embed the graph and scale it so that I have no unwanted edges, and then replace each edge with a path by placing a vertex on each integer co-ordinate of the path. Now the resulting graph is a grid graph where the minimum vertex cover is polynomial time solvable. Why does the reduction not work now? | |
| Dec 1, 2014 at 17:31 | comment | added | Arnaud | Yes. A natural way to ensure that you do not get unwanted edges is to scale your graph so that pairs of paths are always far enough. | |
| Dec 1, 2014 at 15:43 | comment | added | Pavan Sangha | yes this makes sense thanks, if I could ensure that unwanted edges never arose would the initial graph then be the same? I.e the old graph with edges are now replaced by paths? | |
| Dec 1, 2014 at 12:59 | comment | added | Arnaud | Well, the resulting graph is a grid graph yes, but it may not be the same graph as the original one, since you may add unwanted edges when adding disks of radius 1/2 at every integer coordinate on a path. For example if you have vertices at u=(0,0), v=(0,2) and w=(1,1), and an edge from u to v, the vertex you add at (0,1) will be connected to w. | |
| Nov 28, 2014 at 15:41 | comment | added | Pavan Sangha | I think I can explain better where I am getting confused. Suppose I take the grid embedding of the planar graph I know each edge uv has integer length so suppose I place uv intermediate nodes at each interger co-ordinate on the path from u to v then the resulting graph is a grid graph right? | |
| Nov 18, 2014 at 13:36 | comment | added | Arnaud | @PavanSangha See edit. | |
| Nov 18, 2014 at 13:34 | history | edited | Arnaud | CC BY-SA 3.0 |
added 545 characters in body
|
| Nov 18, 2014 at 11:24 | comment | added | Pavan Sangha | So just to clarify the graph they obtain by embedding the planar graph into a grid and then adding unit disks onto the edges is NOT in general a grid graph, unless the initial planar graph is bipartite? | |
| Nov 18, 2014 at 11:01 | comment | added | Pavan Sangha | Yes I was thinking the same thing, and you are right grid graphs are defined as unit disk graphs where vertices take integer co-ordinates with radius 1/2 | |
| Nov 18, 2014 at 0:14 | comment | added | Arnaud | This is probably not the definition used here since any such grid graph is bipartite, which is considered as an exception in their paragraph. | |
| Nov 17, 2014 at 16:58 | comment | added | Pavan Sangha | As far as I am aware a grid graph is a graph where only neighbouring vertices are connected (i.e they have Euclidean distance one) does this change anything? | |
| Nov 16, 2014 at 0:34 | history | answered | Arnaud | CC BY-SA 3.0 |