Parameterized complexity of fair deletion problems

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Parameterized complexity of fair deletion problems
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)