Multitasking capacity: hardness results and improved constructions

DOI10.1137/18M1224672MaRDI QIDQ5220467zbMATH OpenFDO

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

Publication date 26 March 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.02835

zbMATH Keywords

connected matchingshardness of approximationwireless networks

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We consider the problem of determining the maximal $alphain(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 $alpha|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 $alpha$ 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 $n^{1-epsilon}$ 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 $$. Finally, we demonstrate the existence of bipartite graphs with $n$ vertices on each side of average degree $d$, that achieve $alpha=1/2-epsilon$ for matchings of size sufficiently smaller than $n/poly(d)$. This nearly matches the trivial upper bound of $1/2$ on $alpha$ which holds for any graph containing a path of length 3.

Recommendations

• On maximum induced matchings in bipartite graphs
• New results on maximum induced matchings in bipartite graphs and beyond
• Simultaneous matchings: Hardness and approximation
• Tight approximation ratio for Minimum Maximal Matching
• scientific article; zbMATH DE number 5799830

Cites work

• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Approximating maximum independent sets by excluding subgraphs
• Approximation Resistance from Pairwise-Independent Subgroups
• Connected matchings and Hadwiger's conjecture
• Connected matchings in chordal bipartite graphs
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1953189 (Why is no real title available?)
• Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture
• Inapproximability of vertex cover and independent set in bounded degree graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Nearly complete graphs decomposable into large induced matchings and their applications
• On a special case of Hadwiger's conjecture
• On arithmetic progressions of cycle lengths in graphs
• On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
• On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels
• Small topological complete subgraphs of ``dense graphs
• Some optimal inapproximability results

Cited in

(3)

• scientific article; zbMATH DE number 5044336 (Why is no real title available?)
• Erratum to: ``Multitasking capacity: hardness results and improved constructions
• Acyclic, star and injective colouring: a complexity picture for H-free graphs

This page was built for publication: Multitasking capacity: hardness results and improved constructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5220467)