# Theory Seminar: The Maximum Star Forest and The Maximum Carpool Matching Problems

Speaker:
The minimum dominating set problem in a graph $G = (V, E)$ asks to find a minimum size set $D \subseteq V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. It is a well known NP-hard optimization problem that was studied from the 1950s onwards. A greedy algorithm for the minimum dominating set problem yields a $O(\log \Delta)$-approximation ratio, where $\Delta$ is the maximum degree in $G$, and this is the best possible, assuming $P \neq NP$. The maximum spanning star forest problem is the dual problem of the minimum dominating set problem and it asks to find a maximum set $L \subseteq V$ such that every vertex in $L$ is adjacent to at least one member of $V \setminus L$. In other words, the maximum spanning star forest problem, asks to find a spanning star forest (a forest in which each connected component is a star) that maximize the number of edges in the forest.
The maximum carpool matching problem is a generalization of the maximum star forest problem, in which we are given a directed graph $D = (V, A)$, a weight function $w:A \to \mathbb{R}$, and a capacity function $c:V \to \mathbb{N}$. the goal is to find a collection of vertex disjoint in-branching of depth one where the in degree of the roots are limited by the capacity function. that maximize the number of edges in the forest.