Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Parameterized Complexity of Vertex-Partitioning Problems
Speaker:Erik Jan Van Leeuwen
coming from:Utrecht University, Netherlands
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 11 July 2017
Duration:30 Minutes
Building:E1 4
A fundamental graph problem is to recognize whether the vertex set of a graph can be bipartitioned into sets A and B such that G[A] and G[B] satisfy certain properties Pi_A and Pi_B, respectively. This problem is called (Pi_A,Pi_B)-Recognition. Famous examples include the recognition of bipartite, split, and unipolar graphs. We present efficient algorithms for many cases of (Pi_A,Pi_B)-Recognition, based on a technique which we dub inductive recognition. In particular, we give fixed-parameter algorithms for two NP-hard (Pi_A,Pi_B)-Recognition problems, Monopolar Recognition and 2-Subcoloring. We complement our algorithmic results with several hardness results for (Pi_A,Pi_B)-Recognition.

This talk is based on the paper "Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs" by Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen (, which appeared in SWAT 2016 and was selected for a contributed talk at HALG 2017.

Name(s):Davis Issac
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Davis Issac, 07/03/2017 01:07 PM -- Created document.