Timeline for Maximum number of internally vertex-disjoint odd length s-t paths
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 6, 2012 at 14:31 | vote | accept | Bart Jansen | ||
| Mar 6, 2012 at 14:31 | vote | accept | Bart Jansen | ||
| Mar 6, 2012 at 14:31 | |||||
| Mar 6, 2012 at 14:30 | comment | added | Bart Jansen | Thanks for your insight Somnath; the reduction in the paper is very relevant. However, I disagree with your claim that "in the graph constructed, the odd length paths between s and t all have length exactly five"; looking at the example graph in Fig. 5 on page 282 of their paper, (s; w1,1; x1,1; c3; -x1,1; y1,1; z1,1; t) is an odd s-t path of length 7. However, it does seem as if the construction can be used to prove the NP-completeness of my problem; thanks! | |
| Jan 24, 2012 at 6:57 | comment | added | Kris | "Hence the Vertex-Disjoint Odd Length Paths problem is NP-complete." | |
| Jan 23, 2012 at 18:36 | history | edited | Somnath | CC BY-SA 3.0 |
added 2 characters in body
|
| Jan 23, 2012 at 16:49 | history | answered | Somnath | CC BY-SA 3.0 |