2018/09/08 by Noga Alon, Alon, Noga, Jonathan D. Cohen +13
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1809.02835
openalex publication_date 2018/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Alon et al. (NIPS 2018) and is motivated by connectionist models of cognition as well as modeling interference in wireless 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). Towards this end we define bipartite half-covers: A new combinatorial object that may be of independent interest. To the best of our knowledge, the best previous hardness result for the connected matching problem was some constant β>1. Finally, we demonstrate the existence of bipartite graphs with n vertices on each side of average degree d, that achieve α=1/2-ε for matchings of size sufficiently smaller than n/poly(d). This nearly matches the trivial upper bound of 1/2 on α which holds for any graph containing a path of length 3.