Multitasking capacity: Hardness results and improved constructions

We consider the problem of determining the maximal α ∈ (0, 1] such that every matching M of size k (or at most k) in a bipartite graph G contains an induced matching of size at least α |M|. This measure was recently introduced in [N. Alon et al., Adv. Neural Inf. Process. Syst., 2017, pp. 2097{2106] and is motivated by computational models in cognitive neuroscience as well as by modeling interference in radio and communication networks. We prove various hardness results for computing α either exactly or approximately. En route to our results, we also consider the maximum connected matching problem: determining the largest matching N in a graph G such that every two edges in N are connected by an edge. We prove a nearly optimal n1-ϵ hardness of approximation result (under randomized reductions) for connected matching in bipartite graphs (with both sides of cardinality n). Toward this end we define bipartite half-covers: a new combinatorial object that may be of independent interest. To our knowledge, the best previous hardness result for the maximum connected matching problem was that it is hard to approximate within some constant β > 1. Finally, we demonstrate the existence of bipartite graphs with n vertices on each side of average degree d, achieving α= 1/2 - ϵ for matchings of size sufficiently smaller than n/d. This nearly matches the trivial upper bound of 1/2 on α which holds for any graph containing a path of length 3.