Multitasking capacity: Hardness results and improved constructions

Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Yu

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)885-903
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Volume34
Issue number1
DOIs
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Connected matchings
  • Hardness of approximation
  • Matching
  • Wireless networks

Fingerprint Dive into the research topics of 'Multitasking capacity: Hardness results and improved constructions'. Together they form a unique fingerprint.

  • Cite this