Popular branchings and their dual certificates

DOI10.1007/978-3-030-45771-6_18zbMATH Open1503.90149arXiv1912.01854OpenAlexW3016662321MaRDI QIDQ5041748FDOQ5041748

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

Publication date: 14 October 2022

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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 branchings, i.e., directed forests; a branching $B$ is 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 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 popular branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that "approximately popular" branchings always exist.

Full work available at URL: https://arxiv.org/abs/1912.01854

Recommendations

• Popular branchings and their dual certificates
• Popular Matchings: Structure and Algorithms
• Popular matchings: structure and algorithms
• Popular ranking
• Popular matchings

zbMATH Keywords

combinatorial algorithmpopular branchings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Combinatorial optimization. Theory and algorithms.
• Optimum branchings
• College Admissions and the Stability of Marriage
• It is difficult to tell if there is a Condorcet spanning tree
• Popular matchings in the marriage and roommates problems
• Popular spanning trees
• Popular Matchings
• Popular matchings and limits to tractability
• Finding socially best spanning treesî
• Packing rooted directed cuts in a weighted directed graph
• Integer Programming
• Popular mixed matchings
• The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
• The fluid mechanics of liquid democracy
• Binary voting with delegable proxy: an analysis of liquid democracy
• Popular matchings in the stable marriage problem
• A Size-Popularity Tradeoff in the Stable Marriage Problem
• Popular branchings and their dual certificates
• The convergence of iterative delegations in liquid democracy in a social network
• Popularity, mixed matchings, and self-duality
• Popular Half-Integral Matchings.
• Quasi-popular Matchings, Optimality, and Extended Formulations
• Popular matchings with two-sided preferences and one-sided ties

Cited In (4)

• Popular branchings and their dual certificates
• Popular critical matchings in the many-to-many setting
• Finding popular branchings in vertex-weighted directed graphs
• Unveiling the truth in liquid democracy with misinformed voters

This page was built for publication: Popular branchings and their dual certificates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041748)