MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

On the Parameterized Complexity of Grid Contraction

Prafullkumar Tale
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Tuesday, 9 June 2020
13:00
30 Minutes
000
000
Saarbrücken

Abstract

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.

Contact

Sándor Kisfaludi-Bak
--email hidden

Video Broadcast

Yes

Tags, Category, Keywords and additional notes

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.

Sándor Kisfaludi-Bak, 06/03/2020 04:12 PM -- Created document.