{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T08:18:15Z","timestamp":1777623495485,"version":"3.51.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T00:00:00Z","timestamp":1622160000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T00:00:00Z","timestamp":1622160000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"DAE, Government of India","award":["RTI4001"],"award-info":[{"award-number":["RTI4001"]}]},{"DOI":"10.13039\/501100011019","name":"NKFIH","doi-asserted-by":"crossref","award":["K120254"],"award-info":[{"award-number":["K120254"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"crossref"}]},{"name":"HAS","award":["KEP-6\/2017"],"award-info":[{"award-number":["KEP-6\/2017"]}]},{"DOI":"10.13039\/501100003825","name":"Hungarian Academy of Sciences","doi-asserted-by":"crossref","award":["LP2016-3\/2018"],"award-info":[{"award-number":["LP2016-3\/2018"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Cooperation of Excellences Grant","award":["KEP-6\/2018"],"award-info":[{"award-number":["KEP-6\/2018"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["BR 4744\/2-1"],"award-info":[{"award-number":["BR 4744\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let<jats:italic>G<\/jats:italic>be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over<jats:italic>branchings<\/jats:italic>, i.e., directed forests; a branching<jats:italic>B<\/jats:italic>is<jats:italic>popular<\/jats:italic>if<jats:italic>B<\/jats:italic>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<jats:italic>G<\/jats:italic>admits a popular branching or not. We give a characterization of popular branchings in terms of<jats:italic>dual certificates<\/jats:italic>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<jats:italic>popular branching polytope<\/jats:italic>in the original space and also show that our algorithm can be modified to compute a branching with<jats:italic>least unpopularity margin<\/jats:italic>. When preferences are strict rankings, we show that \u201capproximately popular\u201d branchings always exist.<\/jats:p>","DOI":"10.1007\/s10107-021-01659-6","type":"journal-article","created":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T11:04:47Z","timestamp":1622199887000},"page":"567-595","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Popular branchings and their dual certificates"],"prefix":"10.1007","volume":"192","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tam\u00e1s","family":"Kir\u00e1ly","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jannik","family":"Matuschke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrike","family":"Schmidt-Kraepelin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,28]]},"reference":[{"issue":"4","key":"1659_CR1","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/06067328X","volume":"37","author":"DJ Abraham","year":"2007","unstructured":"Abraham, D.J., Irving, R.W., Kavitha, T., Mehlhorn, K.: Popular matchings. SIAM J. Comput. 37(4), 1030\u20131034 (2007)","journal-title":"SIAM J. Comput."},{"key":"1659_CR2","doi-asserted-by":"crossref","unstructured":"Bir\u00f3, P., Irving, R.W., Manlove, D.F.: Popular matchings in the marriage and roommates problems. In: Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), Lecture Notes in Computer Science (LNCS), vol.\u00a06078, pp. 97\u2013108. Springer (2010)","DOI":"10.1007\/978-3-642-13073-1_10"},{"key":"1659_CR3","doi-asserted-by":"crossref","unstructured":"Bloembergen, D., Grossi, D., Lackner, M.: On rational delegations in liquid democracy. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) (2019)","DOI":"10.1609\/aaai.v33i01.33011796"},{"issue":"2","key":"1659_CR4","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1111\/jopp.12065","volume":"24","author":"C Blum","year":"2016","unstructured":"Blum, C., Zuber, C.I.: Liquid democracy: potentials, problems, and perspectives. J. Polit. Philos. 24(2), 162\u2013182 (2016)","journal-title":"J. Polit. Philos."},{"key":"1659_CR5","unstructured":"Brill, M.: Interactive democracy. In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) Blue Sky Ideas Track. pp. 1183\u20131187 (2018)"},{"key":"1659_CR6","doi-asserted-by":"crossref","unstructured":"Christoff, Z., Grossi, D.: Binary voting with delegable proxy: An analysis of liquid democracy. In: Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), pp. 134\u2013150 (2017)","DOI":"10.4204\/EPTCS.251.10"},{"key":"1659_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer Programming, Graduate Texts in Mathematics","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Integer Programming, Graduate Texts in Mathematics, vol. 271. Springer, Berlin (2014)"},{"issue":"4","key":"1659_CR8","doi-asserted-by":"publisher","first-page":"2348","DOI":"10.1137\/16M1076162","volume":"31","author":"\u00c1 Cseh","year":"2017","unstructured":"Cseh, \u00c1., Huang, C.C., Kavitha, T.: Popular matchings with two-sided preferences and one-sided ties. SIAM J. Discrete Math. 31(4), 2348\u20132377 (2017)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1659_CR9","first-page":"209","volume":"172","author":"\u00c1 Cseh","year":"2017","unstructured":"Cseh, \u00c1., Kavitha, T.: Popular edges and dominant matchings. Math. Program. 172(1), 209\u2013229 (2017)","journal-title":"Math. Program."},{"issue":"5","key":"1659_CR10","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1142\/S0129054113500226","volume":"24","author":"A Darmann","year":"2013","unstructured":"Darmann, A.: Popular spanning trees. Int. J. Found. Comput. Sci. 24(5), 655\u2013677 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"1659_CR11","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00186-016-0535-3","volume":"84","author":"A Darmann","year":"2016","unstructured":"Darmann, A.: It is difficult to tell if there is a Condorcet spanning tree. Math. Methods Oper. Res. 84(1), 94\u2013104 (2016)","journal-title":"Math. Methods Oper. Res."},{"issue":"4","key":"1659_CR12","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s11238-010-9228-1","volume":"70","author":"A Darmann","year":"2011","unstructured":"Darmann, A., Klamler, C., Pferschy, U.: Finding socially best spanning trees. Theory Decis. 70(4), 511\u2013527 (2011)","journal-title":"Theory Decis."},{"issue":"4","key":"1659_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Natl. Bur. Stand. 71B(4), 233\u2013240 (1967)","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"1659_CR14","doi-asserted-by":"crossref","unstructured":"Escoffier, B., Gilbert, H., Pass-Lanneau, A.: The convergence of iterative delegations in liquid democracy in a social network. In: Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT), Lecture Notes in Computer Science (LNCS), vol. 11801, pp. 284\u2013297. Springer (2019)","DOI":"10.1007\/978-3-030-30473-7_19"},{"key":"1659_CR15","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Kavitha, T.: Quasi-popular matchings, optimality, and extended formulations. In: Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 325\u2013344 (2020)","DOI":"10.1137\/1.9781611975994.20"},{"key":"1659_CR16","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Kavitha, T., Powers, V., Zhang, X.: Popular matchings and limits to tractability. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2790\u20132809 (2019)","DOI":"10.1137\/1.9781611975482.173"},{"issue":"1","key":"1659_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01580218","volume":"6","author":"DR Fulkerson","year":"1974","unstructured":"Fulkerson, D.R.: Packing rooted directed cuts in a weighted directed graph. Math. Program. 6(1), 1\u201313 (1974)","journal-title":"Math. Program."},{"issue":"1","key":"1659_CR18","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"issue":"3","key":"1659_CR19","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/bs.3830200304","volume":"20","author":"P G\u00e4rdenfors","year":"1975","unstructured":"G\u00e4rdenfors, P.: Match making: assignments based on bilateral preferences. Behav. Sci. 20(3), 166\u2013173 (1975)","journal-title":"Behav. Sci."},{"key":"1659_CR20","doi-asserted-by":"crossref","unstructured":"G\u00f6lz, P., Kahng, A., Mackenzie, S., Procaccia, A.: The fluid mechanics of liquid democracy. In: Proceedings of the 14th International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science (LNCS), vol. 11316, pp. 188\u2013202. Springer (2018)","DOI":"10.1007\/978-3-030-04612-5_13"},{"issue":"2","key":"1659_CR21","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"1659_CR22","doi-asserted-by":"crossref","unstructured":"Gupta, S., Misra, P., Saurabh, S., Zehavi, M.: Popular matching in roommates setting is NP-hard. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2810\u20132822 (2019)","DOI":"10.1137\/1.9781611975482.174"},{"key":"1659_CR23","unstructured":"Hardt, S., Lopes, L.: Google votes: A liquid democracy experiment on a corporate social network. Technical Report, Technical Disclosure Commons (2015)"},{"key":"1659_CR24","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.ic.2012.10.012","volume":"222","author":"CC Huang","year":"2013","unstructured":"Huang, C.C., Kavitha, T.: Popular matchings in the stable marriage problem. Inf. Comput. 222, 180\u2013194 (2013)","journal-title":"Inf. Comput."},{"key":"1659_CR25","doi-asserted-by":"crossref","unstructured":"Huang, C.C., Kavitha, T.: Popularity, mixed matchings, and self-duality. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2294\u20132310 (2017)","DOI":"10.1137\/1.9781611974782.151"},{"issue":"1","key":"1659_CR26","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1137\/120902562","volume":"43","author":"T Kavitha","year":"2014","unstructured":"Kavitha, T.: A size-popularity tradeoff in the stable marriage problem. SIAM J. Comput. 43(1), 52\u201371 (2014)","journal-title":"SIAM J. Comput."},{"key":"1659_CR27","unstructured":"Kavitha, T.: Popular half-integral matchings. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a055, pp. 22:1\u201322:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2016)"},{"key":"1659_CR28","doi-asserted-by":"crossref","unstructured":"Kavitha, T., Kir\u00e1ly, T., Matuschke, J., Schlotter, I., Schmidt-Kraepelin, U.: Popular\u00a0branchings and their dual certificates. Technical Report 1912.01854 (2019). arXiv:1912.01854","DOI":"10.1007\/978-3-030-45771-6_18"},{"issue":"24","key":"1659_CR29","doi-asserted-by":"publisher","first-page":"2679","DOI":"10.1016\/j.tcs.2010.03.028","volume":"412","author":"T Kavitha","year":"2011","unstructured":"Kavitha, T., Mestre, J., Nasre, M.: Popular mixed matchings. Theoret. Comput. Sci. 412(24), 2679\u20132690 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"1659_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization","author":"B Korte","year":"2012","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization. Springer, Berlin (2012)"},{"key":"1659_CR31","unstructured":"Kotsialou, G., Riley, L.: Incentivising participation in liquid democracy with breadth first delegation. In: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 638\u2013644 (2020)"},{"key":"1659_CR32","doi-asserted-by":"crossref","unstructured":"McCutchen, R.M.: The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. In: Proceedings of the 8th Latin American Conference on Theoretical Informatics (LATIN), Lecture Notes in Computer Science (LNCS), vol.\u00a04957, pp. 593\u2013604. Springer (2008)","DOI":"10.1007\/978-3-540-78773-0_51"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01659-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01659-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01659-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,4]],"date-time":"2023-11-04T07:58:13Z","timestamp":1699084693000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01659-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,28]]},"references-count":32,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1659"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01659-6","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,28]]},"assertion":[{"value":"30 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Affiliation 6 was incorrect. Now, it has been corrected","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}