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%2F20%3A10422320" target="_blank" >RIV/00216208:11320/20:10422320 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=rMTC1WfaOC" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=rMTC1WfaOC</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2019.06.001" target="_blank" >10.1016/j.dam.2019.06.001</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

Edge deletion problems are those where the goal is to find a subset of edges such that after its removal the graph satisfies the given graph property. Typically, we want to minimize the number of elements removed. In fair deletion problems, the objective is changed, so the maximum number of deletions in a neighborhood of a single vertex is minimized. We study the parameterized complexity of fair deletion problems concerning the structural parameters such as the tree-width, the path-width, the tree-depth, the size of 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 combined size of the tree-depth and the minimum feedback vertex set number. Moreover, we show that there is no algorithm for fair FO vertex-deletion problem running in time n(o)((3)root k), where n is the size of the graph and k is the sum of the mentioned parameters, provided that the Exponential Time Hypothesis holds. On the other hand, we present 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. (C) 2019 Elsevier B.V. All rights reserved.

Název v anglickém jazyce

Parameterized complexity of fair deletion problems

Popis výsledku anglicky

Edge deletion problems are those where the goal is to find a subset of edges such that after its removal the graph satisfies the given graph property. Typically, we want to minimize the number of elements removed. In fair deletion problems, the objective is changed, so the maximum number of deletions in a neighborhood of a single vertex is minimized. We study the parameterized complexity of fair deletion problems concerning the structural parameters such as the tree-width, the path-width, the tree-depth, the size of 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 combined size of the tree-depth and the minimum feedback vertex set number. Moreover, we show that there is no algorithm for fair FO vertex-deletion problem running in time n(o)((3)root k), where n is the size of the graph and k is the sum of the mentioned parameters, provided that the Exponential Time Hypothesis holds. On the other hand, we present 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. (C) 2019 Elsevier B.V. All rights reserved.

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

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

2020

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

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

278

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

11

Strana od-do

51-61

Kód UT WoS článku

000528194300005

EID výsledku v databázi Scopus

2-s2.0-85067294396