Popular Branchings and Their Dual Certificates

Telikepalli Kavitha, Tamás Király, Jannik Matuschke, Ildikó Schlotter, Ulrike Schmidt-Kraepelin


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-15}

Last modification: 29.12.2020. Please email your comments to Tamás Király!