The Taub Faculty of Computer Science Events and Talks

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.
that maximize the number of edges in the forest.
The maximum spanning star forest and maximum carpool matching problems only been studied in the last decade. In this talk I will present some of the results and the open questions related to these problems.