AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

For a family of graphs GG, the GG-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists F \subseteq E(G) of size at most k such that G/F belongs to GG. Here, G/F is the graph obtained from G by contracting all the edges in F. In this work, we initiate the study of Grid Contraction from the parameterized complexity point of view. We present a single exponential fixed parameter tractable algorithm for this problem. We complement this result by proving that unless \ETH\ fails, there is no sub-exponential FPT algorithm. We also present a polynomial kernel for this problem.

This is a joint work with Saket Saurabh and U\'everton dos Santos Souza.

---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Sándor Kisfaludi-Bak

--email hidden

Yes

passcode not visible

logged in users only

We will record the talk via Zoom.
---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.