Open Access
Abstract
We analyze a common feature of -Kemeny AGGregation ( -KAGG) and -One-Sided Crossing Minimization ( -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 -KAGG—a problem in social choice theory—and for -OSCM—a problem in graph drawing. These algorithms run in time , where is the parameter, and significantly improve the previous best algorithms with running times and , 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 -directed feedback arc set. Our results for the above-guarantee version of -KAGG reveal an interesting contrast. We show that when the number of "votes" in the input to -KAGG is odd the above guarantee version can still be solved in time , while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails (equivalently, unless ).