  Tracking causality (or happened-before relation) between events is useful for
many applications such as debugging and recovery from failures. Consider a
concurrent system with $n$ threads and $m$ objects. For such systems, either a
vector clock of size $n$ is used with one component per thread or a vector
clock of size $m$ is used with one component per object. A natural question is
whether one can use a vector clock of size strictly less than the minimum of
$m$ and $n$ to timestamp events. We give an algorithm in this paper that uses a
hybrid of thread and object components. Our algorithm is guaranteed to return
the minimum number of components necessary for vector clocks. We first consider
the case when the interaction between objects and threads is statically known.
This interaction is modeled by a thread-object bipartite graph. Our algorithm
is based on finding the maximum bipartite matching of such a graph and then
applying K\"{o}nig-Egerv\'{a}ry Theorem to compute the minimum vertex cover to
determine the optimal number of components necessary for the vector clock. We
also propose two mechanisms to compute such an vector clock when computation is
revealed in an online fashion. Evaluation on different types of graphs
indicates that our offline algorithm generates a size vector clock which is
significantly less than the minimum of $m$ and $n$. These mechanisms are more
effective when the underlying bipartite graph is not dense.
