Width Parameterizations for Knot-Free Vertex Deletion on Digraphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

Width Parameterizations for Knot-Free Vertex Deletion on Digraphs


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 in-neighbor 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 so-called OR-model. Deadlock detection is correlated with the recognition of knot-free graphs as well as deadlock resolution is closely related to the Knot-Free Vertex Deletion (KFVD) problem, which consists of determining whether an input graph G has a subset S ⊆ 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 κ, its Kenny-width, are bounded by constants, and we remark that KFVD is para-NP-hard even considering many directed width measures as parameters, but in FPT when parameterized by clique-width; (ii) KFVD can be solved in time 2 O(tw) × n, but assuming ETH it cannot be solved in 2 o(tw) × n O(1) , where tw is the treewidth of the underlying undirected graph. Finally, since the size of a minimum directed feedback vertex set (df v) is an upper bound for the size of a minimum knot-free vertex deletion set, we investigate parameterization by df v and we show that (iii) KFVD can be solved in FPT-time parameterized by either df v + κ or df v + p. Results of (iii) cannot be improved when replacing df v by k due to (i).
Fichier principal
Vignette du fichier
LIPIcs-IPEC-2019-2.pdf (955.63 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-03526774 , version 1 (14-01-2022)





Stéphane Bessy, Marin Bougeret, Alan D.A. Carneiro, Fábio Protti, Uéverton dos Santos Souza. Width Parameterizations for Knot-Free Vertex Deletion on Digraphs. IPEC 2019 - 14th International Symposium on Parameterized and Exact Computation, Sep 2019, Munich, Germany. pp.2:1-2:16, ⟨10.4230/LIPIcs.IPEC.2019.2⟩. ⟨lirmm-03526774⟩
17 View
22 Download



Gmail Facebook X LinkedIn More