On the computational hardness based on linear FPT-reductions Conference Paper

abstract

• The notion of linear fpt-reductions has been recently introduced to derive strong computational lower bounds for well-known NP-hard problems. In this paper, we formally investigate the notion of W[t]-hardness under the linear fpt-reduction, and study the structural properties of the corresponding complexity classes. Additional complexity lower bounds on important computational problems are established. Some observations on structural properties of the standard parameterized hierarchy, the W-hierarchy, are also presented. Springer Science + Business Media, LLC 2006.

authors

• Chen, Jianer

published proceedings

• JOURNAL OF COMBINATORIAL OPTIMIZATION

author list (cited authors)

• Chen, J., Huang, X. Z., Kanj, I. A., & Xia, G.

citation count

• 19

complete list of authors

• Chen, J||Huang, XZ||Kanj, IA||Xia, G

publication date

• March 2006

publisher

• Springer Nature  Publisher

published in

• Journal of Combinatorial Optimization  Journal

keywords

• Complexity
• Fpt-reduction
• Hardness
• Linear

Digital Object Identifier (DOI)

• 10.1007/s10878-006-7137-6

start page

• 231

end page

• 247

volume

• 11

issue

• 2

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2Fs10878-006-7137-6