2026-07-22T14:20:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16876 2024-03-06T10:58:33Z ddc:004 open_access

An Exact Algorithm for Knot-Free Vertex Deletion Ramanujan, M. S. Sahu, Abhishek Saurabh, Saket Verma, Shaily exact algorithm knot-free graphs branching algorithm The study of the Knot-Free Vertex Deletion problem emerges from its application in the resolution of deadlocks called knots, detected in a classical distributed computation model, that is, the OR-model. A strongly connected subgraph Q of a digraph D with at least two vertices is said to be a knot if there is no arc (u,v) of D with u ∈ V(Q) and v ∉ V(Q) (no-out neighbors of the vertices in Q). Given a directed graph D, the Knot-Free Vertex Deletion (KFVD) problem asks to compute a minimum-size subset S ⊂ V(D) such that D[V⧵S] contains no knots. There is no exact algorithm known for the KFVD problem in the literature that is faster than the trivial O^⋆(2ⁿ) brute-force algorithm. In this paper, we obtain the first non-trivial upper bound for KFVD by designing an exact algorithm running in time 𝒪^⋆(1.576ⁿ), where n is the size of the vertex set in D. Schloss Dagstuhl – Leibniz-Zentrum für Informatik M. S. Ramanujan and Abhishek Sahu and Saket Saurabh and Shaily Verma 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.78 urn:nbn:de:0030-drops-168769 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.78 eng https://creativecommons.org/licenses/by/4.0/legalcode