|
Speaker:
Jianer Chen, (Texas A&M University, Department of Computer Science)
Title:
Genus Characterizes the Complexity of
Certain Graph Problems: Some Tight Results
Abstract:
We study the fixed-parameter tractability, subexponential time
computability, and approximability of the well-known NP-hard
problems: INDEPENDENT SET, VERTEX COVER, and DOMINATING SET. We derive
tight results and show that the computational complexity of these
problems, with respect to the above complexity measures, is dependent
on the genus of the underlying graph. For instance, we show that,
under the widely-believed complexity assumption W[1] != FPT,
INDEPENDENT SET on graphs of genus bounded by g_1(n) is fixed
parameter tractable if and only if g_1(n) = o(n^2), and DOMINATING SET
on graphs of genus bounded by g_2(n) is fixed parameter tractable if
and only if g_2(n) = n^{o(1)}. Under the assumption that not all SNP
problems are solvable in subexponential time, we show that the above
three problems on graphs of genus bounded by g_3(n) are solvable in
subexponential time if and only if
g_3(n) = o(n). We also show similar results for the approximability of
these problems.
This is a joint work with I. Kanj, L. Perkovic, E. Sedgwick, and G. Xia.
|