Biclique coverings, rectifier networks and the cost of ε-removal

2014/05/30 by Szabolcs Iván, Ádám D. Lelkes, Iván, Szabolcs +8 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #68R10 #DNA and Biological Computing #Discrete Mathematics (cs.DM) #F.1.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #G.2.2 #acm:68R10 #cs.DM #cs.FL #msc:68R10 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1406.0017

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

arxiv created 2014/05/30 · openalex publication_date 2014/05/30 · arxiv updated 2014/06/03 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/04

Abstract

We relate two complexity notions of bipartite graphs: the minimal weight biclique covering number Cov(G) and the minimal rectifier network size Rect(G) of a bipartite graph G. We show that there exist graphs with Cov(G)≥ Rect(G)^3/2-ε. As a corollary, we establish that there exist nondeterministic finite automata (NFAs) with ε-transitions, having n transitions total such that the smallest equivalent ε-free NFA has Ω(n^3/2-ε) 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.

Citations

• On the ratio of optimal integral and fractional covers

Cited by

• Optimal and Efficient Partite Decompositions of Hypergraphs

Related

• On some lower bounds on the number of bicliques needed to cover a bipartite graph
• On the cost of simulating a parallel Boolean automata network by a block-sequential one
• Fractional coverings, greedy coverings, and rectifier networks
• Rice-like complexity lower bounds for Boolean and uniform automata networks
• On Complementing Unambiguous Automata and Graphs With Many Cliques and Cocliques