Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: The Maximum Star Forest and The Maximum Carpool Matching Problems
event speaker icon
Gilad Kutiel (CS, Technion)
event date icon
Wednesday, 13.12.2017, 12:30
event location icon
Taub 201
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.