Biclique coverings, rectifier networks and the cost of $\epsilon$-removal

Abstract

We relate two complexity notions of bipartite graphs: the minimal weight biclique covering number $\mathrm{Cov}(G)$ and the minimal rectifier network size $\mathrm{Rect}(G)$ of a bipartite graph $G$. We show that there exist graphs with $\mathrm{Cov}(G)\ge \mathrm{Rect}(G{)}^{3/2-\epsilon }$. As a corollary, we establish that there exist nondeterministic finite automata (NFAs) with $\epsilon$-transitions, having $n$ transitions total such that the smallest equivalent $\epsilon$-free NFA has $\Omega (n^{3/2-\epsilon })$ transitions. We also formulate a version of previous bounds for the weighted set cover problem and discuss its connections to giving upper bounds for the possible blow-up.

12 pages, to appear in proceedings of DCFS 2014: 16th International Conference on Descriptional Complexity of Finite-State Systems