Parameterized Complexity of Fair Deletion Problems

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

Result language
angličtina
Original language name
Parameterized Complexity of Fair Deletion Problems
Original language description
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.
Czech name
—
Czech description
—

Type
D - Article in proceedings
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
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)