MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

Sayan Bhattacharya
Theoretical Computer Science Group, Institute of Mathematical Sciences
AG1 Mittagsseminar (own work)

Assistant Professor, Institute of Mathematical Sciences
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 30 June 2015
13:00
60 Minutes
E1 4
024
Saarbrücken

Abstract

We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph $G = (V,E)$, with $|V| = n$ and $|E| =m$, in $o(\sqrt{m}\,)$ time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$ amortized time per update.

For maximum matching, we show how to maintain a $(3+\eps)$ approximation in $O(\min(\sqrt{n}/\epsilon, m^{1/3}/\eps^2))$ {\em amortized} time per update, and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em worst-case} time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld from STOC' 2010.

Contact

Arjit Ghosh
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Appeared in SODA 2015.

This is a joint work with Monika Henzinger (University of Vienna, Austria) and Guiseppe Italiano (University of Rome "Tor Vergata", Italy).

Manuscript: http://arxiv.org/abs/1412.1318

Arjit Ghosh, 06/11/2015 23:34
Arjit Ghosh, 06/11/2015 13:01 -- Created document.