{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:30:41Z","timestamp":1753885841239,"version":"3.41.2"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T00:00:00Z","timestamp":1738022400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"abstract":"\n Consider a directed, rooted graph\n \n \\(G=(V\\cup\\{r\\},E)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n where each vertex in\n \n \\(V\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n has a partial order preference over its incoming edges. The preferences of a vertex naturally extend to preferences over arborescences rooted at\n \n \\(r\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We present a polynomial-time algorithm that decides whether a given input instance admits a popular arborescence, i.e., one for which there is no \u201cmore popular\u201d arborescence.\n <\/jats:p>\n \n In fact, our algorithm solves the more general popular common base problem in the intersection of two matroids: we are given an arbitrary matroid\u00a0\n \n \\(M=(E,\\mathcal{I})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and a partition matroid\n \n \\(M_{\\text{part}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n over\u00a0\n \n \\(E\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where partition classes correspond to a set\u00a0\n \n \\(V\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of agents with\n \n \\(|V|={\\rm rank}(M)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and each agent has a partial order preference over its associated partition class; the problem asks for a common base of\u00a0\n \n \\(M\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(M_{\\text{part}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that there is no \u201cmore popular\u201d common base. Our algorithm is combinatorial, and can be regarded as a primal\u2013dual algorithm. It searches for a solution along with its dual certificate, a chain of subsets of\u00a0\n \n \\(E\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , witnessing its popularity. Our generalized results, expressed in terms of matroids, demonstrate that the identification of agents with vertices of the graph in the popular arborescence problem is not essential.\n <\/jats:p>\n \n We also study the related popular common independent set problem. For the case with weak rankings, we formulate the popular common independent set polytope, and thus show that a minimum-cost popular common independent set can be computed efficiently. By contrast, we prove that it is\n \n \\(\\mathsf{NP}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -hard to compute a minimum-cost popular arborescence, even when rankings are strict.\n <\/jats:p>","DOI":"10.1145\/3715329","type":"journal-article","created":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T15:43:28Z","timestamp":1738079008000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Popular Arborescences and Their Matroid Generalization"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2619-6606","authenticated-orcid":false,"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[{"name":"Tata Institute of Fundamental Research, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9771-4955","authenticated-orcid":false,"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[{"name":"Kyoto University, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0114-8280","authenticated-orcid":false,"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[{"name":"HUN-REN Centre for Economic and Regional Studies, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7316-5434","authenticated-orcid":false,"given":"Yu","family":"Yokoi","sequence":"additional","affiliation":[{"name":"Institute of Science Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,1,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/06067328X"},{"volume-title":"Developments in Operations Research","author":"Bock F. C.","key":"e_1_2_1_2_1","unstructured":"F. C. Bock. 1971. An algorithm to construct a minimum directed spanning tree in a directed network. In Developments in Operations Research, B. Avi-Itzak (Ed.). Gordon and Breach, New York, 29\u201344."},{"volume-title":"Finding and Recognizing Popular Coalition Structures. In AAMAS 2020: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. 195\u2013203","author":"Brandt F.","key":"e_1_2_1_3_1","unstructured":"F. Brandt and M. Bullinger. 2020. Finding and Recognizing Popular Coalition Structures. In AAMAS 2020: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. 195\u2013203."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/S000497270004140X"},{"key":"e_1_2_1_5_1","first-page":"1396","article-title":"On the shortest arborescence of a directed graph","volume":"14","author":"Chu Y.","year":"1965","unstructured":"Y. Chu and T. Liu. 1965. On the shortest arborescence of a directed graph. Scientia Sinica 14 (1965), 1396\u20131400.","journal-title":"Scientia Sinica"},{"key":"e_1_2_1_6_1","unstructured":"M. Condorcet. 1785. Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. L\u2019Imprimerie Royale."},{"key":"e_1_2_1_7_1","first-page":"105","article-title":"Popular matchings. In Trends in computational social choice, Ulle Endriss (Ed.). AI Access","volume":"6","year":"2017","unstructured":"\u00c1. Cseh. 2017. Popular matchings. In Trends in computational social choice, Ulle Endriss (Ed.). AI Access, Chapter 6, 105\u2013122.","journal-title":"Chapter"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113500226"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/s00186-016-0535-3","article-title":"It is difficult to tell if there is a Condorcet spanning tree","volume":"84","author":"Darmann A.","year":"2016","unstructured":"A. Darmann. 2016. It is difficult to tell if there is a Condorcet spanning tree. Mathematical Methods of Operations Research 84, 1 (2016), 94 \u2013 104.","journal-title":"Mathematical Methods of Operations Research"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/s11238-010-9228-1","article-title":"Finding Socially Best Spanning Trees","volume":"70","author":"Darmann A.","year":"2011","unstructured":"A. Darmann, C. Klamler, and U. Pferschy. 2011. Finding Socially Best Spanning Trees. Theory and Decision 70, 4 (2011), 511 \u2013 527.","journal-title":"Theory and Decision"},{"key":"e_1_2_1_11_1","volume-title":"Optimum branchings. Journal of Research of the National Institute of Standards 71B","author":"Edmonds J.","year":"1967","unstructured":"J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Institute of Standards 71B (1967), 233\u2013240."},{"key":"e_1_2_1_12_1","unstructured":"J Edmonds. 1970. Submodular functions matroids and certain polyhedra. In Combinatorial Structures and Their Applications R. Guy H. Hanani N. Sauer and J. Sch\u00f6nheim (Eds.). Gordon and Breach 69\u201387."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90032-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/bs.3830200304"},{"key":"e_1_2_1_16_1","unstructured":"M. Goemans. [n.\u2009d.]. Combinatorial Optimization. http:\/\/www-math.mit.edu\/~goemans\/18453S17\/18453.html."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_18_1","volume-title":"Google Votes: A Liquid Democracy Experiment on a Corporate Social Network. Technical Report. Technical Disclosure Commons.","author":"Hardt S.","year":"2015","unstructured":"S. Hardt and L. Lopes. 2015. Google Votes: A Liquid Democracy Experiment on a Corporate Social Network. Technical Report. Technical Disclosure Commons."},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"Exact and approximation algorithms for weighted matroid intersection","volume":"177","author":"Huang Chien-Chung","year":"2019","unstructured":"Chien-Chung Huang, Naonori Kakimura, and Naoyuki Kamiyama. 2019. Exact and approximation algorithms for weighted matroid intersection. Mathematical Programming 177, 1-2 (2019), 85\u2013112.","journal-title":"Mathematical Programming"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M104918X"},{"volume-title":"SODA 2022: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 103\u2013123","author":"Kavitha T.","key":"e_1_2_1_21_1","unstructured":"T. Kavitha, T. Kir\u00e1ly, J. Matuschke, I. Schlotter, and U. Schmidt-Kraepelin. 2022. The popular assignment problem: when cardinality is more important than popularity. In SODA 2022: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 103\u2013123."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01659-6"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"T. Kavitha T. Kir\u00e1ly J. Matuschke I. Schlotter and U. Schmidt-Kraepelin. 2023. The popular assignment problem: when cardinality is more important than popularity. arXiv:2110.10984 [cs.DS] (full version).","DOI":"10.1137\/1.9781611977073.6"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 3724\u20133746","author":"Kavitha Telikepalli","year":"2024","unstructured":"Telikepalli Kavitha, Kazuhisa Makino, Ildik\u00f3 Schlotter, and Yu Yokoi. 2024. Arborescences, Colorful Forests, and Popularity. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 3724\u20133746."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.03.028"},{"key":"e_1_2_1_26_1","volume-title":"9th Eml\u00e9kt\u00e1bla Workshop (Matching Theory)., 7 pages. https:\/\/users.renyi.hu\/~emlektab\/emlektabla9problems.pdf","author":"Kir\u00e1ly T.","year":"2019","unstructured":"T. Kir\u00e1ly. 2019. Popular arborescences. 9th Eml\u00e9kt\u00e1bla Workshop (Matching Theory)., 7 pages. https:\/\/users.renyi.hu\/~emlektab\/emlektabla9problems.pdf"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134733"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 8th Latin American Conference on Theoretical Informatics (LATIN 2008)","volume":"604","author":"McCutchen R. M.","year":"2008","unstructured":"R. M. McCutchen. 2008. 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 2008) (Lecture Notes in Computer Science, Vol. 4957). Springer, 593\u2013604."},{"key":"e_1_2_1_29_1","unstructured":"S. Merrill and B. Grofman. 1999. A Unified Theory of Voting: Directional and Proximity Spatial Models. Cambridge University Press."},{"issue":"1","key":"e_1_2_1_30_1","doi-asserted-by":"crossref","DOI":"10.1145\/2556951","article-title":"Weighted Popular matchings","volume":"10","author":"Mestre J.","year":"2014","unstructured":"J. Mestre. 2014. Weighted Popular matchings. ACM Transactions on Algorithms 10(1), 2 (2014).","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_2_1_31_1","volume-title":"Finding popular branchings in vertex-weighted directed graphs. Theoretical Computer Science 953","author":"Natsui Kei","year":"2023","unstructured":"Kei Natsui and Kenjiro Takazawa. 2023. Finding popular branchings in vertex-weighted directed graphs. Theoretical Computer Science 953 (2023)."},{"key":"e_1_2_1_33_1","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"Schrijver A.","unstructured":"A. Schrijver. 2003. Combinatorial Optimization - Polyhedra and Efficiency. Vol. 24 of Algorithms and Combinatorics. Springer-Verlag, Berlin."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.11.008"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070103"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715329","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3715329","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:18Z","timestamp":1750295898000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,28]]},"references-count":34,"alternative-id":["10.1145\/3715329"],"URL":"https:\/\/doi.org\/10.1145\/3715329","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,1,28]]},"assertion":[{"value":"2024-01-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-14","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3715329"}}