Research Overview
Our research in Combinatorial Algorithms focuses on designing efficient exact, approximation, and parameterized algorithms for NP-hard problems. By leveraging structural constraints and mathematical properties identified in structural graph theory, we develop algorithms that overcome traditional computational limits on special graph classes.
Major Research Topics
1. Algorithms on Special Graph Classes
- Characterization of Graph Classes: Analyzing the structural properties of restricted graph classes, such as chordal, interval, split, claw-free, and H-free graphs.
- Graph Optimization Problems: Designing approximation and exact algorithms for classic hard problems, including graph coloring (b-coloring, fall coloring), cut problems (d-cuts, Maximum Cut), and vertex deletion.
2. Parameterized Complexity & Kernelization
- Parameterized Complexity Analysis: Analyzing problem complexity in relation to structural parameters rather than just input size to find tractable boundaries.
- Kernelization: Developing polynomial and linear kernels (efficient preprocessing algorithms) for generalized covering, packing, and deletion problems on sparse graph classes.
Selected Publications
- Optimal b-colourings and fall colourings in H-free graphs Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza, and Daniël Paulusma The 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026), 2026.
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes Jungho Ahn, Jinha Kim, and O-joung Kwon Journal of Computer and System Sciences (JCSS), 2026.