We are given a bipartite graph \($G=(A \cup B, E)$\) where each vertex has a preference list ranking its neighbors: in particular, every \($a \in A$\) ranks its neighbors in a strict order of preference, whereas the preference lists of \($b \in B$\) may contain ties. A matching \($M$\) is popular if there is no matching \($M'$\) such that the number of vertices that prefer \($M'$\) to \($M$\) exceeds the number that prefer \($M$\) to \($M'$\). We show that the problem of deciding whether \($G$\) admits a popular matching or not is NP-hard. This is the case even when every \($b \in B$\) either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each \($b \in B$\) puts all its neighbors into a single tie. That is, all neighbors of \($b$\) are tied in \($b’s$\) list and and b desires to be matched to any of them. Our main result is an \($\mathcal{O}(n^2)$\) algorithm (where \($n=|A \cup B|$\)) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in \($B$\) have no preferences and do not care whether they are matched or not.

Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing performs close to optimal (Boguna, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power-law degree distribution with controllable exponent \(\beta\) and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573-585, 2012). For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is \(O((\log n)\)\(^{32/((3-\beta)(5-\beta))})\) (Kiwi and Mitsche. ANALCO, pp. 26-39, 2015). We present two much simpler proofs for an improved upper bound of \(O((\log n)\)\(^{2/(3-\beta)})\) and a lower bound of \(\Omega(\log n)\). If the average degree is bounded from above by some constant, we show that the latter bound is tight by proving an upper bound of \(O(\log n)\).

The performance of large distributed systems crucially depends on efficiently balancing their load. This has motivated a large amount of theoretical research how an imbalanced load vector can be smoothed with local algorithms. For technical reasons, the vast majority of previous work focuses on regular (or almost regular) graphs including symmetric topologies such as grids and hypercubes, and ignores the fact that large networks are often highly heterogenous. We model large scale-free networks by Chung-Lu random graphs and analyze a simple local algorithm for iterative load balancing. On n-node graphs our distributed algorithm balances the load within \(O((log~log~n)^2)\) steps. It does not need to know the exponent \(2<\beta<3\) of the power-law degree distribution or the weights \(w_i\) of the graph model. To the best of our knowledge, this is the first result which shows that load-balancing can be done in double-logarithmic time on realistic graph classes.