Title: COMPUTING MINIMUM DIRECTED FEEDBACK VERTEX SET IN O*(1.9977<sup>n</sup>)
Abstract: Theoretical Computer Science, pp. 70-81 (2007) No AccessCOMPUTING MINIMUM DIRECTED FEEDBACK VERTEX SET IN O*(1.9977n)IGOR RAZGONIGOR RAZGONComputer Science Department, University College Cork, IrelandI dedicate this paper to my son Gabriel Razgon who was born on 14/04/2007, just one day before the ICTCS 2007 abstract submission deadline.https://doi.org/10.1142/9789812770998_0010Cited by:19 PreviousNext AboutSectionsPDF/EPUB ToolsAdd to favoritesDownload CitationsTrack CitationsRecommend to Library ShareShare onFacebookTwitterLinked InRedditEmail Abstract: In this paper we propose an algorithm which, given a directed graph G, finds the minimum directed feedback vertex set (FVS) of G in O*(1.9977n) time and polynomial space. To the best of our knowledge, this is the first algorithm computing the minimum directed FVS faster than in O(2n). The algorithm is based on the branch-and-prune principle. The minimum directed FVS is obtained through computing of the complement, i.e. the maximum induced directed acyclic graph. To evaluate the time complexity, we use the measure-and-conquer strategy according to which the vertices are assigned with weights and the size of the problem is measured in the sum of weights of vertices of the given graph rather than in the number of the vertices. FiguresReferencesRelatedDetailsCited By 19Solving Target Set Selection with Bounded Thresholds Faster than $$2^n$$Ivan Bliznets and Danil Sagunov14 September 2022 | Algorithmica, Vol. 85, No. 2Dynamic thresholding search for the feedback vertex set problemWen Sun, Jin-Kao Hao, Zihao Wu, Wenlong Li and Qinghua Wu10 February 2023 | PeerJ Computer Science, Vol. 9SIVA: A Low Complexity and Optimum Decoding Algorithm for Tail-Biting CodesMohammad Karimzadeh and Mai Vu1 Sep 2021 | IEEE Transactions on Wireless Communications, Vol. 20, No. 92-Approximating Feedback Vertex Set in TournamentsDaniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan and Geevarghese Philip et al.1 Jun 2021 | ACM Transactions on Algorithms, Vol. 17, No. 2On the Feedback Number of 3-Uniform Linear Extremal HypergraphsZhongzheng Tang, Yucong Tang and Zhuo Diao11 December 2021Four Shorts Stories on Surprising Algorithmic Uses of TreewidthDániel Marx20 April 2020Control of multilayer biological networks and applied to target identification of complex diseasesWei Zheng, Dingjie Wang and Xiufen Zou28 May 2019 | BMC Bioinformatics, Vol. 20, No. 1Exact Algorithms via Monotone Local SearchFedor V. Fomin, Serge Gaspers, Daniel Lokshtanov and Saket Saurabh8 March 2019 | Journal of the ACM, Vol. 66, No. 2Controllability of Conjunctive Boolean Networks With Application to Gene RegulationZuguang Gao, Xudong Chen and Tamer Basar1 Jun 2018 | IEEE Transactions on Control of Network Systems, Vol. 5, No. 2State-controlling Sets for Conjunctive Boolean Networks * *This research was supported in part by the O_ce of Naval Research (ONR) MURI grant N-00014-16-1-2710.Zuguang Gao, Xudong Chen and Tamer Başar1 Jul 2017 | IFAC-PapersOnLine, Vol. 50, No. 1Super-polynomial approximation branching algorithmsBruno Escoffier, Vangelis Th. Paschos and Emeric Tourniaire3 November 2016 | RAIRO - Operations Research, Vol. 50, No. 4-5An improved exact algorithm for undirected feedback vertex setMingyu Xiao and Hiroshi Nagamochi19 April 2014 | Journal of Combinatorial Optimization, Vol. 30, No. 2Directed Subset Feedback Vertex Set Is Fixed-Parameter TractableRajesh Chitnis, Marek Cygan, Mohammataghi Hajiaghayi and Dániel Marx13 April 2015 | ACM Transactions on Algorithms, Vol. 11, No. 4A New Linear Kernel for Undirected Planar Feedback Vertex Set: Smaller and SimplerMingyu Xiao1 Jan 2014An Improved Exact Algorithm for Undirected Feedback Vertex SetMingyu Xiao and Hiroshi Nagamochi1 Jan 2013Faster Exact Algorithms for Some Terminal Set ProblemsRajesh Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra and M. S. Ramanujan et al.1 Jan 2013Feedback Vertex Set in Mixed GraphsPaul Bonsma and Daniel Lokshtanov1 Jan 2011Conclusions, Open Problems and Further DirectionsFedor V. Fomin and Dieter Kratsch25 October 2010Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic GraphsHenning Fernau and Daniel Raible Theoretical Computer ScienceMetrics History PDF download
Publication Year: 2007
Publication Date: 2007-09-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 41
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot