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

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 ${\mathcal{O}}^{\text{*}}{\text{(2}}^{\mathcal{O}\text{(}\sqrt{k}\log k\text{)}}\text{)}$, where $k$ is the parameter, and significantly improve the previous best algorithms with running times ${𝒪}^{\mathrm{*}}\mathsf{}\mathrm{(}{\mathsf{\text{1.403}}}^k\mathrm{)}$ and ${𝒪}^{\mathrm{*}}\mathsf{}\mathrm{(}{\mathsf{\text{1.4656}}}^k\mathrm{)}$, 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 ${\mathcal{O}}^{\text{*}}{\text{(2}}^{\mathcal{O}\text{(}\sqrt{k}\log k\text{)}}\text{)}$, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails (equivalently, unless $\text{FPT=M[1]}$).