کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874728 | 1441191 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Kernels for deletion to classes of acyclic digraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a digraph D and an integer k, Directed Feedback Vertex Set (DFVS) asks whether there exists a set of vertices S of size at most k such that F=DâS is DAG. Mnich and van Leeuwen [STACS 2016â] considered the kernelization complexity of DFVS with an additional restriction on F, namely that F must be an out-forest (Out-Forest Vertex Deletion Set), an out-tree (Out-Tree Vertex Deletion Set), or a (directed) pumpkin (Pumpkin Vertex Deletion Set). Their objective was to shed light on the kernelization complexity of DFVS, a well-known open problem in Parameterized Complexity. We improve the kernel sizes of Out-Forest Vertex Deletion Set from O(k3) to O(k2) and of Pumpkin Vertex Deletion Set from O(k18) to O(k3). We also prove that the former kernel size is tight under certain complexity theoretic assumptions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 92, March 2018, Pages 9-21
Journal: Journal of Computer and System Sciences - Volume 92, March 2018, Pages 9-21
نویسندگان
Akanksha Agrawal, Saket Saurabh, Roohani Sharma, Meirav Zehavi,