Research Projects

This project explores key open problems in the parameterized complexity and kernelization of graph modification problems, with a particular focus on efficient data reduction techniques for large-scale graphs. In the era of big data, many computational problems involve massive graph-structured inputs such as social networks, biological networks, and dependency graphs where full-scale algorithms become infeasible. A central algorithmic goal is to develop preprocessing methods that reduce the size of problem instances while preserving the existence (or absence) of solutions. Kernelization provides a formal approach to this challenge: it asks whether, for a given parameter k, any input instance can be efficiently reduced to an equivalent instance of size bounded by a polynomial in k. Such solution-preserving reductions are vital for scalable computing, allowing algorithms to operate effectively even on initially intractable inputs. The project focuses on several important and unresolved graph modification problems: 1. Claw-Free Edge Modification Problems: The project aims to resolve whether the problems of making a graph claw-free (i.e., K1,3-free) via edge deletions, completions, or edits admit polynomial kernels. While these problems are known to be fixed-parameter tractable, it remains open whether they allow efficient preprocessing. Solving this would close a prominent gap in the kernelization complexity landscape and may unlock new structural techniques for graph data reduction. 2. Directed Feedback Vertex Set (DFVS): DFVS is a classical problem with numerous applications, yet it lacks a known polynomial kernel when parameterized by solution size k. This project investigates new structural parameterizations such as the combination of k with graph distance measures like cluster vertex deletion number and modular width to determine whether such combined parameters can enable polynomial kernels. These explorations contribute to a broader understanding of how graph structure influences the compressibility of data. 3. Subset Feedback Problems in Tournaments: The research extends to subset versions of feedback problems in tournaments, specifically: • Subset Feedback Vertex Set in Tournaments (Subset-FVST) • Subset Feedback Arc Set in Tournaments (Subset-FAST) While these problems admit polynomial kernels, this work seeks linear kernels, akin to those known for their non-subset counterparts. Tournaments, due to their highly structured nature, offer an ideal setting to explore such efficient preprocessing methods. 4. Eulerian Strong Component Arc Deletion (Min-DESC): This problem involves deleting arcs so that every strongly connected component becomes Eulerian. It is W[1]-hard in general, but tractable on certain graph classes. The project investigates which classes of digraphs (e.g., tournaments, bounded treewidth graphs) allow for fixed-parameter tractability or polynomial kernels. This could lead to practical data simplification techniques for network flow and circuit design problems.