Parameterized Complexity of Fair Deletion Problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10366745" target="_blank" >RIV/00216208:11320/17:10366745 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007%2F978-3-319-55911-7_45" target="_blank" >https://link.springer.com/chapter/10.1007%2F978-3-319-55911-7_45</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-55911-7_45" target="_blank" >10.1007/978-3-319-55911-7_45</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized Complexity of Fair Deletion Problems

Popis výsledku v původním jazyce

Deletion problems are those where given a graph G and a graph property π, the goal is to find a subset of edges such that after its removal the graph G will satisfy the property π. Typically, we want to minimize the number of elements removed. In fair deletion problems we change the objective: we minimize the maximum number of deletions in a neighborhood of a single vertex. We study the parameterized complexity of fair deletion problems with respect to the structural parameters of the tree-width, the path-width, the size of a minimum feedback vertex set, the neighborhood diversity, and the size of minimum vertex cover of graph G. We prove the W[1]-hardness of the fair FO vertex-deletion problem with respect to the first three parameters combined. Moreover, we show that there is no algorithm for fair FO vertex-deletion problem running in time n^o(k^(1/3)), where n is the size of the graph and k is the sum of the first three mentioned parameters, provided that the Exponential Time Hypothesis holds. On the other hand, we provide an FPT algorithm for the fair MSO edge-deletion problem parameterized by the size of minimum vertex cover and an FPT algorithm for the fair MSO vertex-deletion problem parameterized by the neighborhood diversity.

Název v anglickém jazyce

Parameterized Complexity of Fair Deletion Problems

Popis výsledku anglicky

Deletion problems are those where given a graph G and a graph property π, the goal is to find a subset of edges such that after its removal the graph G will satisfy the property π. Typically, we want to minimize the number of elements removed. In fair deletion problems we change the objective: we minimize the maximum number of deletions in a neighborhood of a single vertex. We study the parameterized complexity of fair deletion problems with respect to the structural parameters of the tree-width, the path-width, the size of a minimum feedback vertex set, the neighborhood diversity, and the size of minimum vertex cover of graph G. We prove the W[1]-hardness of the fair FO vertex-deletion problem with respect to the first three parameters combined. Moreover, we show that there is no algorithm for fair FO vertex-deletion problem running in time n^o(k^(1/3)), where n is the size of the graph and k is the sum of the first three mentioned parameters, provided that the Exponential Time Hypothesis holds. On the other hand, we provide an FPT algorithm for the fair MSO edge-deletion problem parameterized by the size of minimum vertex cover and an FPT algorithm for the fair MSO vertex-deletion problem parameterized by the neighborhood diversity.

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/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

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

Theory and Applications of Models of Computation

ISBN

978-3-319-55910-0

ISSN

1611-3349

e-ISSN

neuvedeno

Počet stran výsledku

15

Strana od-do

628-642

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Bern, Switzerland

Datum konání akce

20. 4. 2017

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

WRD - Celosvětová akce

Kód UT WoS článku

—