Knot-Free Vertex Deletion Exact and Enumeration Algorithms

the size of the problem instance. By definition, problems in NP have a 2poly(n) brute force
algorithm which involves searching through all possible boolean vectors of poly(n) size
for a witness to the problem instance. Under the hypothesis P ̸= NP, we cannot expect
a polynomial time algorithm for NP complete problems. One way to deal with this is to
try and minimise the time and space requirement of superpolynomial algorithms. There
has been immense progress in this area in the last two decades, resulting in non-trivial
exact exponential algorithms for numerous problems, including Chromatic Number,
Hamiltonian Cycle and Satisfiability [MdLC18, Bj¨o16, Hoi20]

We focus on the The Knot-free vertex deletion (KFVD) problem. A knot
K in a directed graph D is a strongly connected component of size greater than two,
without an out-edge which is an arc (u, v) where u ∈ V (K) and v ∈/ V (K). KFVD
problem asks to compute the size of the smallest S ⊆ V (D) such that D[V \ S] does
not have a knot. This problem naturally emerges from its application in deadlock res-
olution since knots are deadlocks in the OR-model of distributed computation. The
fastest known exact algorithm for the KFVD problem in literature [RSSV22] runs in
time O⋆(1.576n). We present ideas from a recent work in which we obtained an exact
algorithm running in time O⋆(1.4549n), where n is the number of vertices in D. We
also prove that the number of inclusion wise minimal KFVD sets is O⋆(1.4549n) and
construct a family of graphs with Ω(1.4422n) minimal KFVD sets.

This is a joint work with Dr. Soumen Maity, Dr. Abhishek Sahu and Dr. Saket Saurabh.