{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:37:06Z","timestamp":1759847826454,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>\n            Given a set of obstacles and two points in the plane, is there a path between the two points that does not cross more than\n            <jats:italic>k<\/jats:italic>\n            different obstacles? Equivalently, can we remove\n            <jats:italic>k<\/jats:italic>\n            obstacles so that there is an obstacle-free path between the two designated points? This is a fundamental NP-hard problem that has undergone a tremendous amount of research work. The problem can be formulated and generalized into the following graph problem: Given a planar graph\n            <jats:italic>G<\/jats:italic>\n            whose vertices are colored by color sets, two designated vertices\n            <jats:italic>s<\/jats:italic>\n            ,\n            <jats:italic>t<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ), and\n            <jats:italic>k<\/jats:italic>\n            \u2208 N, is there an\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            path in\n            <jats:italic>G<\/jats:italic>\n            that uses at most\n            <jats:italic>k<\/jats:italic>\n            colors? If each obstacle is connected, then the resulting graph satisfies the color-connectivity property, namely that each color induces a connected subgraph.\n          <\/jats:p>\n          <jats:p>We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove a set of hardness results, including a result showing that the color-connectivity property is crucial for any hope for fixed-parameter tractable (FPT) algorithms. We also show that our hardness results translate to the geometric instances of the problem.<\/jats:p>\n          <jats:p>\n            We then focus on graphs satisfying the color-connectivity property. We design an FPT algorithm for this problem parameterized by both\n            <jats:italic>k<\/jats:italic>\n            and the treewidth of the graph and extend this result further to obtain an FPT algorithm for the parameterization by both\n            <jats:italic>k<\/jats:italic>\n            and the length of the path. The latter result implies and explains previous FPT results for various obstacle shapes.\n          <\/jats:p>","DOI":"10.1145\/3396573","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T02:39:25Z","timestamp":1592793565000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Colored Path Problem and Its Applications"],"prefix":"10.1145","volume":"16","author":[{"given":"Eduard","family":"Eiben","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, Egham, United Kingdom"}]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[{"name":"School of Computing, DePaul University, Chicago, IL, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,6,21]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1142\/S0218195917500017"},{"volume-title":"Proceedings of the International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS\u201909)","author":"Bereg S.","unstructured":"S. Bereg and D. Kirkpatrick . 2009. Approximating barrier resilience in wireless sensor networks . In Proceedings of the International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS\u201909) . 29--40. S. Bereg and D. Kirkpatrick. 2009. Approximating barrier resilience in wireless sensor networks. In Proceedings of the International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS\u201909). 29--40.","key":"e_1_2_1_2_1"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"Carr R.","unstructured":"R. Carr , S. Doddi , G. Konjevod , and M. Marathe . 2000. On the red-blue set cover problem . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900) . 345--353. R. Carr, S. Doddi, G. Konjevod, and M. Marathe. 2000. On the red-blue set cover problem. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900). 345--353.","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/j.tcs.2014.04.009"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1016\/S0020-0190(97)00127-0"},{"key":"e_1_2_1_6_1","article-title":"Computing shortest paths among curved obstacles in the plane","volume":"11","author":"Chen D.","year":"2015","unstructured":"D. Chen and H. Wang . 2015 . Computing shortest paths among curved obstacles in the plane . ACM Trans. Algor. 11 , 4 (2015), 26:1--26:46. D. Chen and H. Wang. 2015. Computing shortest paths among curved obstacles in the plane. ACM Trans. Algor. 11, 4 (2015), 26:1--26:46.","journal-title":"ACM Trans. Algor."},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1016\/j.tcs.2005.02.003"},{"volume-title":"Proceedings of the International Workshop on Paramerterized and Exact Computations (IWPEC\u201906)","author":"Chen Y.","unstructured":"Y. Chen , M. Grohe , and M. Gr\u00fcber . 2006. On parameterized approximability . In Proceedings of the International Workshop on Paramerterized and Exact Computations (IWPEC\u201906) . 109--120. Y. Chen, M. Grohe, and M. Gr\u00fcber. 2006. On parameterized approximability. In Proceedings of the International Workshop on Paramerterized and Exact Computations (IWPEC\u201906). 109--120.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201988)","author":"de Fraysseix H.","unstructured":"H. de Fraysseix , J. Pach , and R. Pollack . 1988. Small sets supporting F\u00e1ry embeddings of planar graphs . In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201988) . ACM, 426--433. H. de Fraysseix, J. Pach, and R. Pollack. 1988. Small sets supporting F\u00e1ry embeddings of planar graphs. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201988). ACM, 426--433.","key":"e_1_2_1_9_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1007\/BF02122694"},{"key":"e_1_2_1_11_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"R. Diestel . 2012. Graph Theory ( 4 th ed.). Springer . R. Diestel. 2012. Graph Theory (4th ed.). Springer.","edition":"4"},{"doi-asserted-by":"crossref","unstructured":"R. Downey and M. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer Berlin.  R. Downey and M. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer Berlin.","key":"e_1_2_1_12_1","DOI":"10.1007\/978-1-4471-5559-1"},{"volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201918)","author":"Eiben E.","unstructured":"E. Eiben , J. Gemmell , I. Kanj , and A. Youngdahl . 2018. Improved results for minimum constraint removal . In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201918) . AAAI Press. E. Eiben, J. Gemmell, I. Kanj, and A. Youngdahl. 2018. Improved results for minimum constraint removal. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201918). AAAI Press.","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201913)","author":"Erickson L.","unstructured":"L. Erickson and S. LaValle . 2013. A simple, but NP-hard, motion planning problem . In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201913) . AAAI Press. L. Erickson and S. LaValle. 2013. A simple, but NP-hard, motion planning problem. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201913). AAAI Press.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","first-page":"229","article-title":"On straight line representation of planar graphs","volume":"11","author":"F\u00e1ry I.","year":"1948","unstructured":"I. F\u00e1ry . 1948 . On straight line representation of planar graphs . Acta Univ. Sezeged. 11 (1948), 229 -- 233 . I. F\u00e1ry. 1948. On straight line representation of planar graphs. Acta Univ. Sezeged. 11 (1948), 229--233.","journal-title":"Acta Univ. Sezeged."},{"unstructured":"M. Garey and D. Johnson. 1979. Computers and Intractability. W. H. Freeman.  M. Garey and D. Johnson. 1979. Computers and Intractability. W. H. Freeman.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the American Institute of Physics","volume":"1648","author":"Gorbenko A.","unstructured":"A. Gorbenko and V. Popov . 2015. The discrete minimum constraint removal motion planning problem . In Proceedings of the American Institute of Physics , Vol. 1648 . AIP Press. A. Gorbenko and V. Popov. 2015. The discrete minimum constraint removal motion planning problem. In Proceedings of the American Institute of Physics, Vol. 1648. AIP Press."},{"unstructured":"R. L. Graham D. E. Knuth and O. Patashnik. 1994. Concrete Mathematics\u2014A Foundation for Computer Science (2nd ed.). Addison-Wesley.  R. L. Graham D. E. Knuth and O. Patashnik. 1994. Concrete Mathematics\u2014A Foundation for Computer Science (2nd ed.). Addison-Wesley.","key":"e_1_2_1_18_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1016\/j.tcs.2012.12.049"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1177\/0278364913507795"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the European Symposium on Algorithms (LIPIcs)","volume":"87","author":"Hershberger J.","unstructured":"J. Hershberger , N. Kumar , and S. Suri . 2017. Shortest paths in the plane with obstacle violations . In Proceedings of the European Symposium on Algorithms (LIPIcs) , Vol. 87 . 49:1--49:14. J. Hershberger, N. Kumar, and S. Suri. 2017. Shortest paths in the plane with obstacle violations. In Proceedings of the European Symposium on Algorithms (LIPIcs), Vol. 87. 49:1--49:14."},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1137\/S0097539795289604"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1287\/ijoc.1040.0075"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999)","author":"Johnson D.","unstructured":"D. Johnson and M. Szegedy . 1999. What are the least tractable instances of max independent set? In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999) . ACM\/SIAM, 927--928. D. Johnson and M. Szegedy. 1999. What are the least tractable instances of max independent set? In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999). ACM\/SIAM, 927--928.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","volume-title":"Computing bounded-width tree and branch decompositions of k-outerplanar graphs. CoRR abs\/1301.5896","author":"Katsikarelis I.","year":"2013","unstructured":"I. Katsikarelis . 2013. Computing bounded-width tree and branch decompositions of k-outerplanar graphs. CoRR abs\/1301.5896 ( 2013 ). http:\/\/arxiv.org\/abs\/1301.5896 I. Katsikarelis. 2013. Computing bounded-width tree and branch decompositions of k-outerplanar graphs. CoRR abs\/1301.5896 (2013). http:\/\/arxiv.org\/abs\/1301.5896"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1007\/BFb0045375"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1016\/j.comgeo.2018.02.006"},{"volume-title":"Proceedings of the Annual International Conference on Mobile Computing and Networking (MOBICOM\u201905)","author":"Kumar S.","unstructured":"S. Kumar , T.H. Lai , and A. Arora . 2005. Barrier coverage with wireless sensors . In Proceedings of the Annual International Conference on Mobile Computing and Networking (MOBICOM\u201905) . ACM, 284--298. S. Kumar, T.H. Lai, and A. Arora. 2005. Barrier coverage with wireless sensors. In Proceedings of the Annual International Conference on Mobile Computing and Networking (MOBICOM\u201905). ACM, 284--298.","key":"e_1_2_1_28_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1016\/j.jcss.2012.09.001"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1016\/0095-8956(84)90013-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1007\/BF01215352"},{"volume-title":"Proceedings of the International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS\u201912)","author":"Tseng K.","unstructured":"K. Tseng and D. Kirkpatrick . 2012. On barrier resilience of sensor networks . In Proceedings of the International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS\u201912) . 130--144. K. Tseng and D. Kirkpatrick. 2012. On barrier resilience of sensor networks. In Proceedings of the International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS\u201912). 130--144.","key":"e_1_2_1_32_1"},{"volume-title":"Proceedings of the 18th MINI EURO Conference on VNS.","author":"Voss S.","unstructured":"S. Voss , R. Cerulli , A. Fink , and M. Gentili . 2005. Applications of the pilot method to hard modifications of the minimum spanning tree problem . In Proceedings of the 18th MINI EURO Conference on VNS. S. Voss, R. Cerulli, A. Fink, and M. Gentili. 2005. Applications of the pilot method to hard modifications of the minimum spanning tree problem. In Proceedings of the 18th MINI EURO Conference on VNS.","key":"e_1_2_1_33_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201905)","author":"Yuan S.","unstructured":"S. Yuan , S. Varma , and J. Jue . 2005. Minimum-color path problems for reliability in mesh networks . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201905) . 2658--2669. S. Yuan, S. Varma, and J. Jue. 2005. Minimum-color path problems for reliability in mesh networks. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201905). 2658--2669.","key":"e_1_2_1_35_1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396573","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3396573","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:28Z","timestamp":1750199608000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396573"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,21]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3396573"],"URL":"https:\/\/doi.org\/10.1145\/3396573","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,6,21]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}