TR-2019-15

Popular Branchings and Their Dual Certificates

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



Abstract

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:

@techreport{egres-19-15,
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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-15}
}


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