George Osipov is a PhD student at Linköping University.

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

The talk is about the parameterized complexity of MinCSP for equality constraint languages, which are languages over an infinite domain with relations defined by first-order formulas whose only predicate is =. This is a natural class of optimization problems on undirected graphs, including problems such as Multicut, Steiner Multicut, and (under singleton expansion) Multiway Cut. Our main contribution is a classification of MinCSP for all finite equality constraint languages under the natural parameterization. We'll show that these problems are either solvable in FPT time, are W[1]-hard but admit a constant-factor FPT-approximation, or do not admit a constant-factor FPT-approximation unless FPT=W[2]. On the positive side, we obtain an FPT algorithm for a generalization of Multicut with deletable triple cut requests, and show a constant-factor FPT-approximation for Disjunctive Multicut, a generalization where the cut requests come as disjunctions of constant width. The talk is based on joint work with Magnus Wahlström.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.