Popular Arborescences and Their Matroid Generalization

Kavitha, Telikepalli and Makino, Kazuhisa and Schlotter, Ildikó Anna and Yokoi, Yu (2025) Popular Arborescences and Their Matroid Generalization. ACM TRANSACTIONS ON ALGORITHMS, 21 (2). No.-22. ISSN 1549-6325

Text poparb_TALG.pdf - Published Version Restricted to Repository staff only Download (772kB) | Request a copy

Abstract

Consider a directed, rooted graph \(G=(V\cup\{r\},E)\) where each vertex in \(V\) has a partial order preference over its incoming edges. The preferences of a vertex naturally extend to preferences over arborescences rooted at \(r\) . 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 “more popular” arborescence.

Actions (login required)

Edit Item