11 papers
Multiway -Cut is fixed-parameter tractable
Tony Huynh, Eun Jung Kim, Sang-il Oum +2
A connectivity function on a finite set is a function that is submodular and symmetric, with . Given a connectivity function via…
An ErdÅs-Pósa theorem for cycles and faces of distinct lengths
J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6
We show that for every , every graph contains vertex-disjoint cycles of different lengths, or there exists a set with $|X| \in \mathcal…
Fast decremental tree sums in forests
Benjamin Aram Berendsohn, Marek SokoÅowski
We study two fundamental decremental dynamic graph problems. In both problems, we need to maintain a vertex-weighted forest of size under edge deletions, weight updates, and a…
Dynamic Detours
Daniel Dadush, MichaÅ Pilipczuk, Amadeus Reinald +2
Fix a parameter . We give dynamic data structures that for a fully dynamic undirected graph , updated over time by edge insertions and edge deletions, can answe…
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
Sang-il Oum, Marek SokoÅowski
We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining on the empty set. For a connectivity function on an…
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Adam Karczmarz, Wojciech Nadara, Marek SokoÅowski
In this paper, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most i…