Structural parameterizations of Tracking Paths problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00360019" target="_blank" >RIV/68407700:21240/22:00360019 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.tcs.2022.09.009" target="_blank" >https://doi.org/10.1016/j.tcs.2022.09.009</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2022.09.009" target="_blank" >10.1016/j.tcs.2022.09.009</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Structural parameterizations of Tracking Paths problem

Popis výsledku v původním jazyce

Given a graph G with source and destination vertices s,t in V(G) respectively, Tracking Paths asks for a minimum set of vertices T subseteq V(G), such that the sequence of vertices restricted to T encountered in each simple path from s to t is unique. The problem was proven NP-hard [3] and was found to admit a quadratic kernel when parameterized by the size of the desired solution [8]. Following recent trends, for the first time, we study Tracking Paths with respect to structural parameters of the input graph, parameters that measure how far the input graph is, from an easy instance. We prove that Tracking Paths admits fixed-parameter tractable (FPT) algorithms when parameterized by the following parameters: (i) size of a 2-dominating set, (ii) size of cluster vertex deletion set, and (iii) size of split deletion set. En route we also look at Vertex Cover parameterized by the size of edge clique cover and show it fixed-parameter tractable.

Název v anglickém jazyce

Structural parameterizations of Tracking Paths problem

Popis výsledku anglicky

Given a graph G with source and destination vertices s,t in V(G) respectively, Tracking Paths asks for a minimum set of vertices T subseteq V(G), such that the sequence of vertices restricted to T encountered in each simple path from s to t is unique. The problem was proven NP-hard [3] and was found to admit a quadratic kernel when parameterized by the size of the desired solution [8]. Following recent trends, for the first time, we study Tracking Paths with respect to structural parameters of the input graph, parameters that measure how far the input graph is, from an easy instance. We prove that Tracking Paths admits fixed-parameter tractable (FPT) algorithms when parameterized by the following parameters: (i) size of a 2-dominating set, (ii) size of cluster vertex deletion set, and (iii) size of split deletion set. En route we also look at Vertex Cover parameterized by the size of edge clique cover and show it fixed-parameter tractable.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

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 periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

1879-2294

Svazek periodika

934

Číslo periodika v rámci svazku

October

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

12

Strana od-do

91-102

Kód UT WoS článku

000886060100007

EID výsledku v databázi Scopus

2-s2.0-85139080527