Representative Sets of Product Families

Abstract

A subfamily ${\mathcal{F}}^{\prime }$ of a set family $\mathcal{F}$ is said to $q$-{\em represent} $\mathcal{F}$ if for every $A\in \mathcal{F}$ and $B$ of size $q$ such that $A\cap B=\varnothing$ there exists a set $A^{\prime }\in {\mathcal{F}}^{\prime }$ such that $A^{\prime }\cap B=\varnothing$. In this paper, we consider the efficient computation of $q$-representative sets for {\em product} families $\mathcal{F}$. A family $\mathcal{F}$ is a product family if there exist families $\mathcal{A}$ and $\mathcal{B}$ such that $\mathcal{F}=\{A\cup B:A\in \mathcal{A},B\in \mathcal{B},A\cap B=\varnothing \}$. Our main technical contribution is an algorithm which given $\mathcal{A}$, $\mathcal{B}$ and $q$ computes a $q$-representative family ${\mathcal{F}}^{\prime }$ of $\mathcal{F}$. The running time of our algorithm is sublinear in $|\mathcal{F}|$ for many choices of $\mathcal{A}$, $\mathcal{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 $\mathcal{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 $\mathcal{F}$ from $\mathcal{A}$ and $\mathcal{B}$, and then computes the $q$-representative family ${\mathcal{F}}^{\prime }$ from $\mathcal{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.

arXiv admin note: substantial text overlap with arXiv:1304.4626

References in corpus (2)

• Finding and counting vertex-colored subtrees
• Constrained multilinear detection for faster functional motif discovery