Breaking the All Subsets Barrier for Min k-Cut

Autor:	Lokshtanov, Daniel, Saurabh, Saket, Surianarayanan, Vaishali
Jazyk:	angličtina
Rok vydání:	2023
Předmět:	graph algorithms k-way cut Theory of computation → Parameterized complexity and exact algorithms exponential algorithms min k-cut Exact algorithms
DOI:	10.4230/lipics.icalp.2023.90
Popis:	In the Min k-Cut problem, the input is a graph G and an integer k. The task is to find a partition of the vertex set of G into k parts, while minimizing the number of edges that go between different parts of the partition. The problem is NP-complete, and admits a simple 3ⁿ⋅n^𝒪(1) time dynamic programming algorithm, which can be improved to a 2ⁿ⋅n^𝒪(1) time algorithm using the fast subset convolution framework by Björklund et al. [STOC'07]. In this paper we give an algorithm for Min k-Cut with running time 𝒪((2-ε)ⁿ), for ε > 10^{-50}. This is the first algorithm for Min k-Cut with running time 𝒪(cⁿ) for c < 2. LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 90:1-90:19
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e9f50714c2163a3d48d9074604ecdc9a Zobrazit plný text záznamu