Social Choice Meets Graph Drawing: How to Get Subexponential Time Algorithms for Ranking and Drawing Problems

作     者：Henning Fernau Fedor V.Fomin Daniel Lokshtanov Matthias Mnich Geevarghese Philip Saket Saurabh 

作者机构：FB 4-Abteilung Informatikwissenschaften Universitt Trier D-54286 TrierGermany the Department of Informatics University of Bergen N-5020 Bergen Norway Max-Planck-Institut fr Informatik D-66123 Saarbrcken Germany the Institute of Mathematical Sciences Chennai - 600113 India 

出 版 物：《Tsinghua Science and Technology》 (清华大学学报（自然科学版（英文版）)

年 卷 期：2014年第19卷第4期

页      面：374-386页

核心收录：

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

基　　金：supported by a GermanNorwegian PPP grant supported by the Indo-German Max Planck Center for Computer Science (IMPECS) 

主　　题：Kemeny aggregation one sided crossing minimization parameterized complexity subexponential time algorithms social choice theory graph drawing directed feedback arc set 

摘      要：We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.