Finding popular branchings in vertex-weighted digraphs
share
Popular matchings have been intensively studied recently as a relaxed concept of stable matchings. By applying the concept of popular matchings to branchings in directed graphs, Kavitha et al. (2020) introduced popular branchings. In a directed graph G=(V_G,E_G), each vertex has preferences over its incoming edges. For branchings B_1 and B_2 in G, a vertex v∈ V_G prefers B_1 to B_2 if v prefers its incoming edge of B_1 to that of B_2, where having an arbitrary incoming edge is preferred to having none, and B_1 is more popular than B_2 if the number of vertices that prefer B_1 is greater than the number of vertices that prefer B_2. A branching B is called a popular branching if there is no branching more popular than B. Kavitha et al. (2020) proposed an algorithm for finding a popular branching when the preferences of each vertex are given by a strict partial order. The validity of this algorithm is proved by utilizing classical theorems on the duality of weighted arborescences. In this paper, we generalize popular branchings to weighted popular branchings in vertex-weighted directed graphs in the same manner as weighted popular matchings by Mestre (2014). We give an algorithm for finding a weighted popular branching, which extends the algorithm of Kavitha et al., when the preferences of each vertex are given by a total preorder and the weights satisfy certain conditions. Our algorithm includes elaborated procedures resulting from the vertex-weights, and its validity is proved by extending the argument of the duality of weighted arborescences.
READ FULL TEXT