{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T05:05:39Z","timestamp":1774933539619,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2006,3]]},"DOI":"10.1007\/s10878-006-7137-6","type":"journal-article","created":{"date-parts":[[2006,5,4]],"date-time":"2006-05-04T20:10:21Z","timestamp":1146773421000},"page":"231-247","source":"Crossref","is-referenced-by-count":23,"title":["On the computational hardness based on linear FPT-reductions"],"prefix":"10.1007","volume":"11","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiuzhen","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7137_CR1","doi-asserted-by":"crossref","unstructured":"Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (1999) Complexity and Approximation \u2013 Combinatorial Optimization problems and their Approximability Properties, Springer","DOI":"10.1007\/978-3-642-58412-1"},{"key":"7137_CR2","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"S Ausiello","year":"1980","unstructured":"Ausiello S, D'Atri A, Protasi M (1980) Structure preserving reductions among convex optimization problems, Journal of Computer and System Sciences 21:136\u2013153","journal-title":"Journal of Computer and System Sciences"},{"key":"7137_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender HL, Fellows MR (1995) $W[2]$-hardness of precedence constrained $k$-processor scheduling, Operations Research Letters 18, pp. 93\u201397","DOI":"10.1016\/0167-6377(95)00031-9"},{"key":"7137_CR4","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L Cai","year":"1997","unstructured":"Cai L, Chen J (1997) On fixed parameter tractability and approximability of NP optimization problems, Journal of Computer and System Sciences 54:465\u2013474","journal-title":"Journal of Computer and System Sciences"},{"key":"7137_CR5","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L Cai","year":"2003","unstructured":"Cai L, Juedes D (2003) On the existence of subexponential parameterized algorithms, Journal of Computer and System Sciences 67:789\u2013807","journal-title":"Journal of Computer and System Sciences"},{"key":"7137_CR6","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1016\/S0304-3975(01)00343-7","volume":"289","author":"L Cai","year":"2002","unstructured":"Cai L, Juedes D, Kanj IA (2002) Inapproximability of non NP-hard optimization problems, Theoretical Computer Science 289:553\u2013571","journal-title":"Theoretical Computer Science"},{"key":"7137_CR7","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M Cesati","year":"1997","unstructured":"Cesati M, Trevisan L (1997) On the efficiency of polynomial time approximation schemes, Information Processing Letters 64:165\u2013171","journal-title":"Information Processing Letters"},{"key":"7137_CR8","doi-asserted-by":"crossref","unstructured":"Chen J (1991) Characterizing parallel hierarchy by reducibilities, Information Processing Letters 39:303\u2013307","DOI":"10.1016\/0020-0190(91)90003-Z"},{"key":"7137_CR9","doi-asserted-by":"crossref","unstructured":"Chen J, Chor B, Fellows M, Huang X, Juedes D, Kanj I, Xia G (2004) Tight lower bounds for certain parameterized NP-hard problems, Proc. 19th Annual IEEE Conference on Computational Complexity (CCC 2004), pp. 150\u2013160","DOI":"10.1109\/CCC.2004.1313826"},{"key":"7137_CR10","doi-asserted-by":"crossref","unstructured":"Chen J, Huang X, Kanj I, Xia G (2004) Linear FPT reductions and computational lower bounds, Proc. 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 212\u2013221","DOI":"10.1145\/1007352.1007391"},{"key":"7137_CR11","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen J, Kanj IA, Jia W (2001) Vertex cover: further observations and further improvements, Journal of Algorithms 41:280\u2013301","journal-title":"Journal of Algorithms"},{"key":"7137_CR12","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S1571-0661(04)81014-4","volume":"78","author":"R Downey","year":"2003","unstructured":"Downey R, Estivill-Castro V, Fellows M, Prieto-Rodriguez E, Rosamond F (2003) Cutting up is hard to do: the parameterized complexity of $k$-cut and related problems, Electronic Notes in Theoretical Computer Science 78:205\u2013218","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"7137_CR13","doi-asserted-by":"crossref","unstructured":"Downey R, Evans P, Fellows M (1993) Parameterized learning complexity, Proc. 6th ACM Workshop on Computational Learning Theory, pp. 51\u201357","DOI":"10.1145\/168304.168311"},{"key":"7137_CR14","unstructured":"Downey RG, Fellows MR (1994) Parameterized computational feasibility, Proc. 2nd Cornell Workshop on Feasible Mathematics, Feasible Mathematics II, Clote P, and Remmel J, eds., Birkhauser Boston,pp. 219\u2013244"},{"key":"7137_CR15","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey RG, Fellows MR (1995) Fixed-parameter tractability and completeness I: basic results, SIAM Journal on Computing 24:873\u2013921","journal-title":"SIAM Journal on Computing"},{"key":"7137_CR16","doi-asserted-by":"crossref","unstructured":"Downey RG, Fellows MR (1999) Parameterized Complexity, Springer-Verlag","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"7137_CR17","doi-asserted-by":"crossref","unstructured":"Flum J, Grohe M (2004) Model-checking problems as a basis for parameterized intractability, Proc. 19th IEEE Symposium on Logic in Computer Science, (LICS'04), pp. 388\u2013397","DOI":"10.1109\/LICS.2004.1319633"},{"key":"7137_CR18","doi-asserted-by":"crossref","unstructured":"Flum J, Grohe M, Weyer M (2004) Bounded fixed-parameter tractability and log2 n nondeterministic bits, Proc. 31st International Colloquium on Automata, Languages, and Programming (ICALP 2004), Lecture Notes in Computer Science 3142:555\u2013567","DOI":"10.1007\/978-3-540-27836-8_48"},{"key":"7137_CR19","doi-asserted-by":"crossref","unstructured":"Grohe M (2001) The parameterized complexity of database queries, Proc. 20th ACM Symposium on Principles of Database Systems, (PODS'01), pp. 82\u201392","DOI":"10.1145\/375551.375564"},{"key":"7137_CR20","unstructured":"Huang X (2004) Parameterized Complexity and Polynomial-time Approximation Schemes, Ph.D. Dissertation, Department of Computer Science, Texas A&M University, December"},{"key":"7137_CR21","unstructured":"Papadimitriou CH (1995) Computational Complexity, Addison-Wesley Pub., Reading, Mass"},{"key":"7137_CR22","doi-asserted-by":"crossref","unstructured":"Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes, Journal of Computer and System Sciences 43:425\u2013440","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"7137_CR23","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1006\/jcss.1996.0058","volume":"53","author":"CH Papadimitriou","year":"1996","unstructured":"Papadimitriou CH, Yannakakis M (1996) On limited nondeterminism and the complexity of VC dimension, Journal of Computer and System Sciences 53:161\u2013170","journal-title":"Journal of Computer and System Sciences"},{"key":"7137_CR24","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"CH Papadimitriou","year":"1999","unstructured":"Papadimitriou CH, Yannakakis M (1999) On the complexity of database queries, Journal of Computer and System Sciences 58:407\u2013427","journal-title":"Journal of Computer and System Sciences"},{"key":"7137_CR25","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak K (2003) On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems, Journal of Computer and System Sciences 67:757\u2013771","journal-title":"Journal of Computer and System Sciences"},{"key":"7137_CR26","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"RE Tarjan","year":"1977","unstructured":"Tarjan RE and Trojanowski AE (1977) Finding a maximum independent set, SIAM J. Comput. 6:537\u2013546","journal-title":"SIAM J. Comput."},{"key":"7137_CR27","doi-asserted-by":"crossref","unstructured":"Van Horn K, Martinez T (1994) The minimum feature set problem, Neural Networks 7:491\u2013494","DOI":"10.1016\/0893-6080(94)90082-5"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-7137-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-006-7137-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-7137-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:09Z","timestamp":1559276289000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-006-7137-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["7137"],"URL":"https:\/\/doi.org\/10.1007\/s10878-006-7137-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]}}}