Campus Event Calendar
Event Entry
What and Who
Parameterized Complexity of Vertex-Partitioning Problems
Erik Jan Van Leeuwen
Utrecht University, Netherlands
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 11 July 2017
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
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 (http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.14), which appeared in SWAT 2016 and was selected for a contributed talk at HALG 2017.
Contact
Davis Issac
--email hidden
passcode not visible
logged in users only
Davis Issac, 07/03/2017 13:07 -- Created document.