기초과학연구원 이산수학그룹
We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an guarantee when the function is monotone …
Let $\mathcal{F}$ be a family of graphs, and let $p$ and $r$ be nonnegative integers. The $(p,r,\mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$, there exists …
Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender, Cornelissen, and van der Wegen, we consider the parameterized problem of computing a decomposition. …
By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 Pólya asked for which (0, 1)-matrices A it is possible to change …
For fixed integers $r\ge 3, e\ge 3$, and $v\ge r+1$, let $f_r(n,v,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ …
A linear $3$-graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices. A linear $3$-graph is called a Steiner triple system if …
Finding the smallest integer $N=ES_d(n)$ such that in every configuration of $N$ points in $\mathbb{R}^d$ in general position, there exist $n$ points in convex position is one of the most …
The disjoint paths logic, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate $\mathsf{dp}_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ …
Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded …
Various types of independent sets have been studied for decades. As an example, the minimum number of maximal independent sets in a connected graph of given order is easy to …