Bessy, Stéphane ;
Bougeret, Marin ;
Carneiro, Alan D. A. ;
Protti, Fábio ;
Souza, Uéverton S.
Width Parameterizations for KnotFree Vertex Deletion on Digraphs
Abstract
A knot in a directed graph G is a strongly connected subgraph Q of G with at least two vertices, such that no vertex in V(Q) is an inneighbor of a vertex in V(G)\V(Q). Knots are important graph structures, because they characterize the existence of deadlocks in a classical distributed computation model, the socalled ORmodel. Deadlock detection is correlated with the recognition of knotfree graphs as well as deadlock resolution is closely related to the KnotFree Vertex Deletion (KFVD) problem, which consists of determining whether an input graph G has a subset S subseteq V(G) of size at most k such that G[V\S] contains no knot. Because of natural applications in deadlock resolution, KFVD is closely related to Directed Feedback Vertex Set. In this paper we focus on graph width measure parameterizations for KFVD. First, we show that: (i) KFVD parameterized by the size of the solution k is W[1]hard even when p, the length of a longest directed path of the input graph, as well as kappa, its Kennywidth, are bounded by constants, and we remark that KFVD is paraNPhard even considering many directed width measures as parameters, but in FPT when parameterized by cliquewidth; (ii) KFVD can be solved in time 2^{O(tw)} x n, but assuming ETH it cannot be solved in 2^{o(tw)} x n^{O(1)}, where tw is the treewidth of the underlying undirected graph. Finally, since the size of a minimum directed feedback vertex set (dfv) is an upper bound for the size of a minimum knotfree vertex deletion set, we investigate parameterization by dfv and we show that (iii) KFVD can be solved in FPTtime parameterized by either dfv+kappa or dfv+p. Results of (iii) cannot be improved when replacing dfv by k due to (i).
BibTeX  Entry
@InProceedings{bessy_et_al:LIPIcs:2019:11463,
author = {St{\'e}phane Bessy and Marin Bougeret and Alan D. A. Carneiro and F{\'a}bio Protti and U{\'e}verton S. Souza},
title = {{Width Parameterizations for KnotFree Vertex Deletion on Digraphs}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {2:12:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771290},
ISSN = {18688969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11463},
URN = {urn:nbn:de:0030drops114631},
doi = {10.4230/LIPIcs.IPEC.2019.2},
annote = {Keywords: Knot, deadlock, width measure, FPT, W[1]hard, directed feedback vertex set}
}
04.12.2019
Keywords: 

Knot, deadlock, width measure, FPT, W[1]hard, directed feedback vertex set 
Seminar: 

14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Issue date: 

2019 
Date of publication: 

04.12.2019 