Animation scientifique
Date : 8 octobre 2026 15:00 - Salle :salle A002
Inclusive and Exclusive vertex splits to specific graph classesPraneet Kumar Patra - LIMOS Groupe de travail : ALCOLOCO |
Graph modification problems have long been a central theme in both classical and parameterized complexity theory. These problems typically aim to transform a given graph into one satisfying certain desired structural properties by applying a limited number of allowed operations. Over the years, a wide range of graph operations-such as vertex deletion, edge contraction, and edge editing have been extensively studied in this context. Each of these operations provides unique insights into the structural behavior of graphs and serves as a foundation for developing efficient algorithms and complexity classifications.
In this talk, we will discuss one such operation, specifically the vertex splits. Here, a single vertex can be split into two copies, where the edges can be distributed by dis-jointly distributing the neighbors (Exclusive vertex split) or distributing the neighbors while allowing repetitions (Inclusive vertex Splits). In particular we will focus on giving polynomial runtime algorithms (on general graphs) when the desired final graph class is a Linear Forest (disjoint collection of paths) or a collection of cycles. We will focus on how the algorithms naturally arise from the underlying structure of these graph classes.
This is a part of a joint work with Prof Soumen Maity, Ajinkya Gaikwad, Hitendra Kumar, Harsh Sanklecha and S Padmapriya.