
- This event has passed.
CO Seminar – Faezeh Motiei
November 29, 2024 @ 12:30 - 13:30
Location: MF 12
Speaker: Faezeh Motiei (TU/e)
Title: Deletion to F-free Graph Classes and Tree-Like Structures
Abstract:
The Π-Deletion problem asks whether it is possible to remove up to k vertices from a graph such that the remaining graph satisfies a given property Π. Many classic optimization problems, such as Vertex Cover and Feedback Vertex Set, can be framed as Π-Deletion problems. After transforming the input graph into a simplified graph by removing a limited number of vertices, special properties can be imposed on the new graph and some hard problems become computationally easier.
The Deletion to Scattered Graph Classes problem is a variant of Π-Deletion where the goal is to remove up to k vertices so that each connected component of the resulting graph belongs to a specified class. This problem has a fixed-parameter tractable algorithm for the case where classes are defined by a finite set of forbidden induced subgraphs, but this does not cover the tree-like classes as they cannot be characterized by a finite set of forbidden patterns.
In this talk, we present an algorithm for identifying subgraphs with tree-like properties and at most k vertices in its neighborhood, demonstrating how it can be used as a subroutine to solve specific instances of the Deletion to Scattered Graph Classes problem.