Exact Exponential Algorithms & Knot-Free Vertex Deletion

Abstract

A knot K in a directed graph D = (V, E) is a strongly connected subgraph of D with at least two vertices, such that there is no arc (u, v) of D with u in V (K) and v not in V (K). Given a directed graph D = (V, E), we study Knot-Free Vertex Deletion (KFVD), where the goal is to remove the minimum number of vertices, such that the resulting graph does not have any knots. This problem naturally emerges from its application in deadlock resolution in the OR-model of distributed computation. KFVD is known to be NP-complete even on graphs of maximum degree 4. The fastest known exact algorithm in literature for KFVD runs in time O*(1.576^n). We present an improved exact algorithm running in time O*(1.4549^n), where n is the number of vertices in D. We also prove that the number of inclusion wise minimal knot-free vertex deletion sets is O*(1.4549^n) and show that this bound is almost optimal by constructing a family of graphs with Ω(1.4422^n) minimal knot-free vertex deletion sets.