Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams
- Submitting institution
-
University of Bristol
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 238980917
- Type
- E - Conference contribution
- DOI
-
10.4230/LIPIcs.CCC.2020.30
- Title of conference / published proceedings
- 35th Computational Complexity Conference (CCC 2020)
- First page
- 1
- Volume
- -
- Issue
- -
- ISSN
- 1868-8969
- Open access status
- Compliant
- Month of publication
- July
- Year of publication
- 2020
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
D - Fundamentals of Computing
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This work completely settles the space complexity of Maximum Matching and Minimum Vertex Cover in dynamic graph streams. Previous lower bounds (Assadi et al. [SODA'16], Konrad [ESA'15]) only hold for a subclass of algorithms and rely on complex combinatorial constructions. This technique is much simpler and has therefore the potential to be widely applied for proving other dynamic graph stream lower bounds. Both previously known lower bounds (Assadi et al., Konrad) had significant impact on the field. This paper renders these results obsolete. The paper forms the basis of Konrad's recently awarded EPSRC New Investigator Award (EP/V010611/1).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
