  A subfamily ${\cal F}'$ of a set family ${\cal F}$ is said to $q$-{\em
represent} ${\cal F}$ if for every $A \in {\cal F}$ and $B$ of size $q$ such
that $A \cap B = \emptyset$ there exists a set $A' \in {\cal F}'$ such that $A'
\cap B = \emptyset$. In this paper, we consider the efficient computation of
$q$-representative sets for {\em product} families ${\cal F}$. A family ${\cal
F}$ is a product family if there exist families ${\cal A}$ and ${\cal B}$ such
that ${\cal F} = \{A \cup B~:~A \in {\cal A}, B \in {\cal B}, A \cap B =
\emptyset\}$. Our main technical contribution is an algorithm which given
${\cal A}$, ${\cal B}$ and $q$ computes a $q$-representative family ${\cal F}'$
of ${\cal F}$. The running time of our algorithm is sublinear in $|{\cal F}|$
for many choices of ${\cal A}$, ${\cal B}$ and $q$ which occur naturally in
several dynamic programming algorithms. We also give an algorithm for the
computation of $q$-representative sets for product families ${\cal F}$ in the
more general setting where $q$-representation also involves independence in a
matroid in addition to disjointness. This algorithm considerably outperforms
the naive approach where one first computes ${\cal F}$ from ${\cal A}$ and
${\cal B}$, and then computes the $q$-representative family ${\cal F}'$ from
${\cal F}$.
  We give two applications of our new algorithms for computing
$q$-representative sets for product families. The first is a
$3.8408^{k}n^{O(1)}$ deterministic algorithm for the Multilinear Monomial
Detection ($k$-MlD) problem. The second is a significant improvement of
deterministic dynamic programming algorithms for "connectivity problems" on
graphs of bounded treewidth.
