Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F21%3A00354887" target="_blank" >RIV/68407700:21240/21:00354887 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-030-92702-8_2" target="_blank" >https://doi.org/10.1007/978-3-030-92702-8_2</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-92702-8_2" target="_blank" >10.1007/978-3-030-92702-8_2</a>
Alternative languages
Result language
angličtina
Original language name
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Original language description
Consider a vertex-weighted graph G with a source s and a target t. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique. In this work, we derive a factor 66-approximation algorithm for Tracking Paths in weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approximation of the closely related r -Fault Tolerant Feedback Vertex Set problem. There, for a fixed integer r and a given vertex-weighted graph G, the task is to find a minimum weight set of vertices intersecting every cycle of G in at least r+1 vertices. We give a factor O(r^2) approximation algorithm for r -Fault Tolerant Feedback Vertex Set if r is a constant.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Approximation and Online Algorithms - 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6-10, 2021, Revised Selected Papers
ISBN
978-3-030-92701-1
ISSN
0302-9743
e-ISSN
—
Number of pages
16
Pages from-to
23-38
Publisher name
Springer, Cham
Place of publication
—
Event location
Lisabon (Online)
Event date
Sep 6, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—