Description
EGERVÁRY SZEMINÁRIUM
Absztrakt: Popular branchings can be defined analogously to popular matchings: each node has a partial order on the incoming edges, and a branching is popular if it does not lose a head-to-head election against any other branching (being a root is the least preferred option). One motivation for this notion comes from liquid democracy, where voters have the choice to delegate their vote to others whom they consider to be more knowledgeable on the issue at hand. In the talk, I show that the existence of popular branchings can be decided in polynomial time. In the case of weak rankings (preference orders with ties), even the minimum cost popular branching and the minimum unpopularity margin problems are polynomial-time solvable. In contrast, these two problems are NP-hard for general partial orders.
Joint work with Telikepalli Kavitha, Jannik Matuschke, Ildikó Schlotter, and Ulrike Schmidt-Kraepelin.