|
Let $G$ be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over {\em branchings}, i.e., directed forests; a branching $B$ is {\em popular} if $B$ does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if $G$ admits a popular branching or not. We give a characterization of popular branchings in terms of {\em dual certificates} and use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate the {\em popular branching polytope} in the original space and also show that our algorithm can be modified to compute a branching with {\em least unpopularity margin}. When preferences are strict rankings, we show that "approximately popular" branchings always exist.
Bibtex entry:
| AUTHOR | = | {Kavitha, Telikepalli and Kir{\'a}ly, Tam{\'a}s and Matuschke, Jannik and Schlotter, Ildik{\'o} and Schmidt-Kraepelin, Ulrike}, |
| TITLE | = | {Popular Branchings and Their Dual Certificates}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2019}, |
| NUMBER | = | {TR-2019-15} |