{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T14:28:32Z","timestamp":1784557712349,"version":"3.55.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,1,3]],"date-time":"2008-01-03T00:00:00Z","timestamp":1199318400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s00453-007-9148-9","type":"journal-article","created":{"date-parts":[[2008,1,2]],"date-time":"2008-01-02T14:00:18Z","timestamp":1199282418000},"page":"203-225","source":"Crossref","is-referenced-by-count":65,"title":["Short Cycles Make W-hard Problems Hard: FPT\u00a0Algorithms for W-hard Problems in Graphs with\u00a0no\u00a0Short Cycles"],"prefix":"10.1007","volume":"52","author":[{"given":"Venkatesh","family":"Raman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,1,3]]},"reference":[{"issue":"3","key":"9148_CR1","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial time data reduction for dominating set. J. ACM 51(3), 363\u2013384 (2004)","journal-title":"J. ACM"},{"key":"9148_CR2","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.jcss.2004.03.007","volume":"71","author":"J. Alber","year":"2005","unstructured":"Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: A refined search tree technique for dominating set on planar graphs. J. Comput. Syst. Sci. 71, 385\u2013405 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20133","key":"9148_CR3","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0166-218X(03)00387-1","volume":"132","author":"V.E. Alekseev","year":"2003","unstructured":"Alekseev, V.E.: On easy and hard hereditary classes of graphs with respect to the independent set problem. Discrete Appl. Math. 132(1\u20133), 17\u201326 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"9148_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.disc.2004.04.010","volume":"285","author":"V.E. Alekseev","year":"2004","unstructured":"Alekseev, V.E., Korobitsyn, D.V., Lozin, V.V.: Boundary classes of graphs for the dominating set problem. Discrete Math. 285(1\u20133), 1\u20136 (2004)","journal-title":"Discrete Math."},{"issue":"6","key":"9148_CR5","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0020-0190(02)00434-9","volume":"85","author":"M. Bl\u00e4ser","year":"2003","unstructured":"Bl\u00e4ser, M.: Computing small partial coverings. Inf. Process. Lett. 85(6), 327\u2013331 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"9148_CR6","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(97)00101-1","volume":"209","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Threshold dominating sets and an improved characterization of W[2]. Theor. Comput. Sci. 209(1\u20132), 123\u2013140 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9148_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"2","key":"9148_CR8","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/S0097539797323571","volume":"29","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R., Vardy, A., Whittle, G.: The parametrized complexity of some fundamental problems in coding theory. SIAM J. Comput. 29(2), 545\u2013570 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9148_CR9","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(99)00185-7","volume":"100","author":"R.G. Downey","year":"2000","unstructured":"Downey, R.G., Fellows, M.R., Raman, V.: The complexity of irredundant sets parameterized by size. Discrete Appl. Math. 100(3), 155\u2013167 (2000)","journal-title":"Discrete Appl. Math."},{"key":"9148_CR10","doi-asserted-by":"crossref","unstructured":"Duh, R., F\u00fcrer, M.: Approximation of k-set cover by semi-local optimization. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 256\u2013264 (1997)","DOI":"10.1145\/258533.258599"},{"key":"9148_CR11","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"4","key":"9148_CR12","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln\u2009n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9148_CR13","unstructured":"Fernau, H.: Parameterized algorithms: a graph-theoretic approach. Habilitationsschrift, Universit\u00e4t T\u00fcbingen, T\u00fcbingen, Germany (2005)"},{"key":"9148_CR14","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9148_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/11847250_17","volume-title":"Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC)","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V.: Finding a minimum feedback vertex set in time O(1.7548 n ). In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC). Lecture Notes in Computer Science, vol. 4169, pp. 184\u2013191. Springer, Berlin (2006)"},{"key":"9148_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/11534273_5","volume-title":"Proceeding of the 9th International Workshop Algorithms and Data Structures (WADS)","author":"J. Guo","year":"2005","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized vertex cover problems. In: Proceeding of the 9th International Workshop Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 3608, pp. 36\u201348. Springer, Berlin (2005)"},{"issue":"3","key":"9148_CR17","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"9148_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04650-0","volume-title":"Extremal Combinatorics","author":"S. Jukna","year":"2001","unstructured":"Jukna, S.: Extremal Combinatorics. Springer, Berlin (2001)"},{"issue":"2","key":"9148_CR19","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S. Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9148_CR20","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Peleg, D.: On choosing a dense subgraph. In: Proceeding of the 34th Annual Symposium on Foundations of Computer Science (FOCS), pp. 692\u2013701 (1993)","DOI":"10.1109\/SFCS.1993.366818"},{"key":"9148_CR21","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e0sz","year":"1975","unstructured":"Lov\u00e0sz, L.: On the ratio of optimal fractional and integral covers. Discrete Math. 13, 383\u2013390 (1975)","journal-title":"Discrete Math."},{"key":"9148_CR22","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, London (2006)"},{"key":"9148_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/11785293_29","volume-title":"Proceeding of the 10th Scandinavian Workshop on Algorithm Theory (SWAT)","author":"V. Raman","year":"2006","unstructured":"Raman, V., Saurabh, S.: Triangles, 4-cycles and parameterized (in-)tractability. In: Proceeding of the 10th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol. 4059, pp. 304\u2013315. Springer, Berlin (2006)"},{"key":"9148_CR24","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9148-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9148-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9148-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:01Z","timestamp":1559123101000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9148-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,3]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9148"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9148-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,3]]}}}