Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

—

Počet stran výsledku

16

Strana od-do

23-38

Název nakladatele

Springer, Cham

Místo vydání

—

Místo konání akce

Lisabon (Online)

Datum konání akce

6. 9. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—