{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T02:52:09Z","timestamp":1786157529132,"version":"3.56.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662531730","type":"print"},{"value":"9783662531747","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_33","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T14:50:06Z","timestamp":1470322206000},"page":"472-486","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT"],"prefix":"10.1007","author":[{"given":"Bart M. P.","family":"Jansen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"issue":"7","key":"33_CR1","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for d-Hitting set. J. Comput. Syst. Sci. 76(7), 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"33_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"key":"33_CR3","doi-asserted-by":"crossref","unstructured":"B\u00e9jar, R., H\u00e4hnle, R., Many\u00e0, F.: A modular reduction of regular logic to classical logic. In: Proceedings of 31st International Symposium on Multiple-Valued Logic, pp. 221\u2013226 (2001)","DOI":"10.1109\/ISMVL.2001.924576"},{"key":"33_CR4","unstructured":"Bringmann, K., Hermelin, D., Mnich, M., van Leeuwen, E.J.: Parameterized complexity dichotomy for Steiner multicut. In: Proceedings of 32nd STACS, pp. 157\u2013170 (2015)"},{"issue":"1","key":"33_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0166-218X(85)90057-5","volume":"10","author":"D Coppersmith","year":"1985","unstructured":"Coppersmith, D., Vishkin, U.: Solving NP-hard problems in \u2018almost trees\u2019: vertex cover. Discrete App. Math. 10(1), 27\u201345 (1985)","journal-title":"Discrete App. Math."},{"issue":"4","key":"33_CR6","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1\u201323:27 (2014)","journal-title":"J. ACM"},{"issue":"2","key":"33_CR7","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs. ACM Trans. Algorithms 11(2), 13 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"33_CR8","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)"},{"issue":"3","key":"33_CR9","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Jansen, B.M.P., Rosamond, F.: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity. Eur. J. Combin. 34(3), 541\u2013566 (2013)","journal-title":"Eur. J. Combin."},{"issue":"1","key":"33_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(00)00387-5","volume":"113","author":"J Fiala","year":"2001","unstructured":"Fiala, J., Kloks, T., Kratochv\u00edl, J.J.: Fixed-parameter complexity of $$\\lambda $$ -labelings. Discrete Appl. Math. 113(1), 59\u201372 (2001)","journal-title":"Discrete Appl. Math."},{"key":"33_CR11","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, New York (2006)"},{"issue":"4","key":"33_CR12","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1016\/j.jda.2005.07.005","volume":"4","author":"J Guo","year":"2006","unstructured":"Guo, J., Niedermeier, R.: Exact algorithms and applications for tree-like weighted set cover. J. Discrete Algorithms 4(4), 608\u2013622 (2006)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"33_CR13","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"33_CR14","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P.: On structural parameterizations of hitting set: hitting paths in graphs using 2-SAT. CoRR, abs\/1507.05890 (2015)","DOI":"10.1007\/978-3-662-53174-7_33"},{"key":"33_CR15","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"33_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-319-06089-7_17","volume-title":"Theory and Applications of Models of Computation","author":"M Lu","year":"2014","unstructured":"Lu, M., Liu, T., Tong, W., Lin, G., Xu, K.: Set cover, set packing and hitting set for tree convex and tree-like set systems. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol. 8402, pp. 248\u2013258. Springer, Heidelberg (2014)"},{"key":"33_CR17","unstructured":"Many\u00e0, F.: The 2-SAT problem in signed CNF-formulas. In: Multiple-Valued Logic (2000)"},{"key":"33_CR18","unstructured":"Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of 27th STACS, pp. 17\u201332 (2010)"},{"key":"33_CR19","unstructured":"Trick, M.A.: Induced subtrees of a tree and the set packing problem. Technical Report 377, Institute for Mathematics and Its Applications (1987)"},{"key":"33_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.tcs.2013.01.029","volume":"494","author":"J Uhlmann","year":"2013","unstructured":"Uhlmann, J., Weller, M.: Two-layer planarization parameterized by feedback edge set. Theor. Comput. Sci. 494, 99\u2013111 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR21","unstructured":"Wahlstr\u00f6m, M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. thesis, Link\u00f6pings universitet, Sweden (2007)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T12:53:42Z","timestamp":1749041622000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"5 August 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Garching","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2015","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2015","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2015","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2015","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}