Length 3 Edge-Disjoint Paths Is NP-Hard
In 2003, it was claimed that the following problem was solvable in polynomial time: do there exist k edge-disjoint paths of length exactly 3 between vertices s and t in a given graph? The proof was flawed, and in this note we show that this problem is NP-hard. We use a reduction from Partial Orienta...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
SP Birkhäuser Verlag Basel
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106920 https://orcid.org/0000-0001-5813-5029 |
| _version_ | 1826201138995658752 |
|---|---|
| author | Alpert, Hannah Iglesias, Jennifer |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Alpert, Hannah Iglesias, Jennifer |
| author_sort | Alpert, Hannah |
| collection | MIT |
| description | In 2003, it was claimed that the following problem was solvable in polynomial time: do there exist k edge-disjoint paths of length exactly 3 between vertices s and t in a given graph? The proof was flawed, and in this note we show that this problem is NP-hard. We use a reduction from Partial Orientation, a problem recently shown by Pálvölgyi to be NP-hard. |
| first_indexed | 2024-09-23T11:47:08Z |
| format | Article |
| id | mit-1721.1/106920 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:47:08Z |
| publishDate | 2017 |
| publisher | SP Birkhäuser Verlag Basel |
| record_format | dspace |
| spelling | mit-1721.1/1069202022-09-27T21:53:31Z Length 3 Edge-Disjoint Paths Is NP-Hard Alpert, Hannah Iglesias, Jennifer Massachusetts Institute of Technology. Department of Mathematics Alpert, Hannah In 2003, it was claimed that the following problem was solvable in polynomial time: do there exist k edge-disjoint paths of length exactly 3 between vertices s and t in a given graph? The proof was flawed, and in this note we show that this problem is NP-hard. We use a reduction from Partial Orientation, a problem recently shown by Pálvölgyi to be NP-hard. 2017-02-10T22:36:18Z 2017-02-10T22:36:18Z 2012-03 2016-08-18T15:40:14Z Article http://purl.org/eprint/type/JournalArticle 1016-3328 1420-8954 http://hdl.handle.net/1721.1/106920 Alpert, Hannah, and Jennifer Iglesias. “Length 3 Edge-Disjoint Paths Is NP-Hard.” Comput. Complex. 21, no. 3 (March 21, 2012): 511–513. https://orcid.org/0000-0001-5813-5029 en http://dx.doi.org/10.1007/s00037-012-0038-4 computational complexity Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Basel AG application/pdf SP Birkhäuser Verlag Basel SP Birkhäuser Verlag Basel |
| spellingShingle | Alpert, Hannah Iglesias, Jennifer Length 3 Edge-Disjoint Paths Is NP-Hard |
| title | Length 3 Edge-Disjoint Paths Is NP-Hard |
| title_full | Length 3 Edge-Disjoint Paths Is NP-Hard |
| title_fullStr | Length 3 Edge-Disjoint Paths Is NP-Hard |
| title_full_unstemmed | Length 3 Edge-Disjoint Paths Is NP-Hard |
| title_short | Length 3 Edge-Disjoint Paths Is NP-Hard |
| title_sort | length 3 edge disjoint paths is np hard |
| url | http://hdl.handle.net/1721.1/106920 https://orcid.org/0000-0001-5813-5029 |
| work_keys_str_mv | AT alperthannah length3edgedisjointpathsisnphard AT iglesiasjennifer length3edgedisjointpathsisnphard |