기초과학연구원 이산수학그룹
Given a graph class $\mathcal{H}$, the task of the $\mathcal{H}$-Square Root problem is to decide whether an input graph G has a square root H that belongs to $\mathcal{H}$. We are interested in the parameterized complexity of the problem for classes $\mathcal{H}$ that are composed by the graphs at vertex deletion distance at most $k$ …
Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a vertex subset S of size at most k, such that G-S is an interval graph. A polynomial kernel for a parameterized problem is a polynomial time preprocessing algorithm that outputs an equivalent instance of the problem whose size is bounded by …
Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a …
In 2007, Chepoi, Estellon, and Vaxès conjectured that there exists a universal constant $c>0$ such that the following holds for every positive integers $r$ and $k$, and every planar graph $G$: Either $G$ contains $k$ vertex-disjoint balls of radius $r$, or there is a subset of vertices of size at most $c k$ meeting all …