Please use this identifier to cite or link to this item: http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/7953
Title: Exact Exponential Algorithms & Knot-Free Vertex Deletion
Authors: MAITY, SOUMEN
SAURABH, SAKET
E S, AJAYKRISHNAN
Dept. of Mathematics
20181004
Keywords: Theoretical Computer Science
Algorithm Design
Graph Algorithms
Knot-Free Vertex Deletion
Exact Exponential Algorithms
Branching Algorithms
Measure and Conquer
Issue Date: May-2023
Citation: 67
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.
URI: http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/7953
Appears in Collections:MS THESES

Files in This Item:
File Description SizeFormat 
20181004_Ajaykrishnan_ES_MS_ThesisMS Thesis1.09 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.