Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.54
URN: urn:nbn:de:0030-drops-115500
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11550/
Eppstein, David ; Goodrich, Michael T. ; Liu, James A. ; Matias, Pedro
Tracking Paths in Planar Graphs
| pdf-format: |
|
Abstract
We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et al. [Banik et al., 2017]. Given an undirected graph with a source s and a destination t, find the smallest subset of vertices whose intersection with any s-t path results in a unique sequence. In this paper, we show that this problem remains NP-complete when the graph is planar and we give a 4-approximation algorithm in this setting. We also show, via Courcelle's theorem, that it can be solved in linear time for graphs of bounded-clique width, when its clique decomposition is given in advance.
BibTeX - Entry
@InProceedings{eppstein_et_al:LIPIcs:2019:11550,
author = {David Eppstein and Michael T. Goodrich and James A. Liu and Pedro Matias},
title = {{Tracking Paths in Planar Graphs}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {54:1--54:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11550},
URN = {urn:nbn:de:0030-drops-115500},
doi = {10.4230/LIPIcs.ISAAC.2019.54},
annote = {Keywords: Approximation Algorithm, Courcelle's Theorem, Clique-Width, Planar, 3-SAT, Graph Algorithms, NP-Hardness}
}
| Keywords: | Approximation Algorithm, Courcelle's Theorem, Clique-Width, Planar, 3-SAT, Graph Algorithms, NP-Hardness | |
| Seminar: | 30th International Symposium on Algorithms and Computation (ISAAC 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 28.11.2019 |
