Zobrazeno 1 - 4
of 4
pro vyhledávání: '"Wang, Xiuhan"'
In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no $f(k)\cdot n^{k^{o(1/\log\log k)}}$-time algorithm that can decide whether an $n$-vertex graph contains a clique of size $k$ or contains no clique of size $k/2$,
Externí odkaz:
http://arxiv.org/abs/2304.02943
In this paper, we prove that it is W[2]-hard to approximate k-SetCover within any constant ratio. Our proof is built upon the recently developed threshold graph composition technique. We propose a strong notion of threshold graphs and use a new compo
Externí odkaz:
http://arxiv.org/abs/2202.04377
Given a simple graph $G$ and an integer $k$, the goal of $k$-Clique problem is to decide if $G$ contains a complete subgraph of size $k$. We say an algorithm approximates $k$-Clique within a factor $g(k)$ if it can find a clique of size at least $k /
Externí odkaz:
http://arxiv.org/abs/2111.14033
In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6eb1f46101838cef2066c2601d83c24e