## Abstrakti

Vertex connectivity a classic extensively-studied problem. Given an integer k, its goal is to decide if an n-node m-edge graph can be disconnected by removing k vertices. Although a linear-time algorithm was postulated since 1974 [Aho, Hopcroft and Ullman], and despite its sibling problem of edge connectivity being resolved over two decades ago [Karger STOC’96], so far no vertex connectivity algorithms are faster than O(n^{2}) time even for k = 4 and m = O(n). In the simplest case where m = O(n) and k = O(1), the O(n^{2}) bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory’69]. For higher m, O(m) time is known for k ≤ 3 [Tarjan FOCS’71; Hopcroft, Tarjan SICOMP’73], the first O(n^{2}) time is from [Kanevsky, Ramachandran, FOCS’87] for k = 4 and from [Nagamochi, Ibaraki, Algorithmica’92] for k = O(1). For general k and m, the best bound is Õ (min(kn^{2}, n^{ω} + nk^{ω} )) [Henzinger, Rao, Gabow FOCS’96; Linial, Lovász, Wigderson FOCS’86] where Õ hides polylogarithmic terms and ω < 2.38 is the matrix multiplication exponent. In this paper, we present a randomized Monte Carlo algorithm with Õ (m + k^{7}/^{3}n^{4}/^{3}) time for any k = O(n). This gives the first subquadratic time bound for any 4 ≤ k ≤ o(n^{2}/^{7}) (subquadratic time refers to O(m) + o(n^{2}) time.) and improves all above classic bounds for all k ≤ n^{0.44}. We also present a new randomized Monte Carlo (1 + ϵ)-approximation algorithm that is strictly faster than the previous Henzinger’s 2-approximation algorithm [J. Algorithms’97] and all previous exact algorithms. The story is the same for the directed case, where our exact Õ (min(km^{2}/^{3}n, km^{4}/^{3}))-time for any k = O(n) and (1 + ϵ)-approximation algorithms improve all previous exact bounds. Additionally, our algorithm is the first approximation algorithm on directed graphs. The key to our results is to avoid computing single-source connectivity, which was needed by all previous exact algorithms and is not known to admit o(n^{2}) time. Instead, we design the first local algorithm for computing vertex connectivity; without reading the whole graph, our algorithm can find a separator of size at most k or certify that there is no separator of size at most k “near” a given seed node.

Alkuperäiskieli | Englanti |
---|---|

Otsikko | STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing |

Toimittajat | Moses Charikar, Edith Cohen |

Kustantaja | ACM |

Sivut | 241-252 |

Sivumäärä | 12 |

ISBN (elektroninen) | 9781450367059 |

DOI - pysyväislinkit | |

Tila | Julkaistu - 23 kesäkuuta 2019 |

OKM-julkaisutyyppi | A4 Artikkeli konferenssijulkaisuussa |

Tapahtuma | ACM Symposium on Theory of Computing - Phoenix, Yhdysvallat Kesto: 23 kesäkuuta 2019 → 26 kesäkuuta 2019 Konferenssinumero: 51 |

### Julkaisusarja

Nimi | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (painettu) | 0737-8017 |

### Conference

Conference | ACM Symposium on Theory of Computing |
---|---|

Lyhennettä | STOC |

Maa | Yhdysvallat |

Kaupunki | Phoenix |

Ajanjakso | 23/06/2019 → 26/06/2019 |