Multitasking Capacity: Hardness Results and Improved Constructions

Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths +5

We consider the problem of determining the maximal $\alpha \in (0,1]$ such that every matching $M$ of size $k$ (or at most $k$) in a bipartite graph $G$ contains an induced matching of s…