On knot-free vertex deletion: Fine-grained parameterized complexity analysis of a deadlock resolution graph problem.

A knot in a directed graph G is a strongly connected subgraph Q of G with size at least two, such that no vertex in V (Q) is an in-neighbor of a vertex in V (G) ∖ V (Q). Knots are important graph structures in Computer Science because they characterize the existence of deadlocks in a classical distributed computation model, the so-called OR-model. Given a directed graph G , and a positive integer k , the Knot-Free Vertex Deletion (KFVD) problem consists of determining whether G has a subset S ⊆ V (G) with size at most k such that G [ V ∖ S ] contains no knot. KFVD is an NP-complete graph problem with natural applications in deadlock resolution. In this paper, we present a parameterized complexity analysis of KFVD. We prove that: KFVD is W[1]-hard when parameterized by the size of the solution; it can be solved in 2 k log ⁡ φ ⋅ n O (1) time, but assuming SETH, it cannot be solved in (2 − ϵ) k log ⁡ φ ⋅ n O (1) time, where φ is the size of the largest strongly connected subgraph of G ; it can be solved in 2 ϕ ⋅ n O (1) time, but assuming ETH, it cannot be solved in 2 o (ϕ) ⋅ n O (1) time, where ϕ is the number of vertices with out-degree at most k ; it can be solved in 2 O (t w log ⁡ t w) ⋅ n O (1) time, but assuming ETH it cannot be solved in 2 o (t w) ⋅ n O (1) time, where tw is the treewidth of the underlying undirected graph; and, it can be solved in FPT time when parameterized by the clique-width of the directed graph. In addition, lower bounds for kernelization are also provided. [ABSTRACT FROM AUTHOR]