{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:06:44Z","timestamp":1742922404354,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031159138"},{"type":"electronic","value":"9783031159145"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-15914-5_7","type":"book-chapter","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T11:14:22Z","timestamp":1664536462000},"page":"84-97","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Problems Hard for\u00a0Treewidth but\u00a0Easy for\u00a0Stable Gonality"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9297-3330","authenticated-orcid":false,"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3787-2550","authenticated-orcid":false,"given":"Gunther","family":"Cornelissen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0899-6925","authenticated-orcid":false,"given":"Marieke","family":"van der Wegen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,1]]},"reference":[{"key":"7_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows \u2013 Theory, Algorithms and Applications. Prentice Hall (1993)"},{"key":"7_CR2","unstructured":"Alexandersson, P.: NP-complete variants of some classical graph problems. CoRR, abs\/2001.04120 (2020). arXiv:2001.04120"},{"issue":"6","key":"7_CR3","doi-asserted-by":"publisher","first-page":"613","DOI":"10.2140\/ant.2008.2.613","volume":"2","author":"M Baker","year":"2008","unstructured":"Baker, M.: Specialization of linear systems from curves to graphs. Algebra Number Theory 2(6), 613\u2013653 (2008). https:\/\/doi.org\/10.2140\/ant.2008.2.613. With an appendix by Brian Conrad","journal-title":"Algebra Number Theory"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"2914","DOI":"10.1093\/imrn\/rnp037","volume":"15","author":"M Baker","year":"2009","unstructured":"Baker, M., Norine, S.: Harmonic morphisms and hyperelliptic graphs. Int. Math. Res. Not. IMRN 15, 2914\u20132955 (2009). https:\/\/doi.org\/10.1093\/imrn\/rnp037","journal-title":"Int. Math. Res. Not. IMRN"},{"issue":"10","key":"7_CR5","doi-asserted-by":"publisher","first-page":"2909","DOI":"10.1007\/s00453-017-0358-5","volume":"80","author":"B Bliem","year":"2017","unstructured":"Bliem, B., Woltran, S.: Complexity of secure sets. Algorithmica 80(10), 2909\u20132940 (2017). https:\/\/doi.org\/10.1007\/s00453-017-0358-5","journal-title":"Algorithmica"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/j.dam.2018.04.001","volume":"251","author":"B Bliem","year":"2018","unstructured":"Bliem, B., Woltran, S.: Defensive alliances in graphs of bounded treewidth. Discrete Appl. Math. 251, 334\u2013339 (2018). https:\/\/doi.org\/10.1016\/j.dam.2018.04.001","journal-title":"Discrete Appl. Math."},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.tcs.2020.02.013","volume":"815","author":"JM Bodewes","year":"2020","unstructured":"Bodewes, J.M., Bodlaender, H.L., Cornelissen, G., van der Wegen, M.: Recognizing hyperelliptic graphs in polynomial time. Theoret. Comput. Sci. 815, 121\u2013146 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.02.013","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR8","unstructured":"Bodlaender, H.L., Cornelissen, G., van der Wegen, M.: Problems hard for treewidth but easy for stable gonality. CoRR, abs\/2202.06838 (2022). arXiv:2202.06838"},{"key":"7_CR9","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H.: On the parameterized complexity of computing tree-partitions. CoRR, abs\/2206.11832 (2022). arXiv:2206.11832"},{"key":"7_CR10","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H.: XNLP-completeness for parameterized problems on graphs with a linear structure. CoRR, abs\/2201.13119 (2022). arXiv:2201.13119"},{"key":"7_CR11","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Nederlof, J., Swennenhuis, C.M.F.: Parameterized problems complete for nondeterministic FPT time and logarithmic space. In: Proceedings 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pp. 193\u2013204 (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00027","DOI":"10.1109\/FOCS52979.2021.00027"},{"key":"7_CR12","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Inf. Comput. 167(2), 86\u2013119 (2001). https:\/\/doi.org\/10.1006\/inco.2000.2958","DOI":"10.1006\/inco.2000.2958"},{"key":"7_CR13","doi-asserted-by":"publisher","unstructured":"Cornelissen, G., Kato, F., Kool, J.: A combinatorial Li-Yau inequality and rational points on curves. Math. Ann. (10), 211\u2013258 (2014). https:\/\/doi.org\/10.1007\/s00208-014-1067-x","DOI":"10.1007\/s00208-014-1067-x"},{"issue":"1","key":"7_CR14","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput. 85(1), 12\u201375 (1990). https:\/\/doi.org\/10.1016\/0890-5401(90)90043-H","journal-title":"Inform. and Comput."},{"key":"7_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"7_CR16","doi-asserted-by":"publisher","unstructured":"van Dobben de Bruyn, J., Gijswijt, D.: Treewidth is a lower bound on graph gonality. Algebr. Comb. 3(4), 941\u2013953 (2020). https:\/\/doi.org\/10.5802\/alco.124","DOI":"10.5802\/alco.124"},{"key":"7_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-79723-4_9","volume-title":"Parameterized and Exact Computation","author":"M Dom","year":"2008","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 78\u201390. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_9"},{"key":"7_CR18","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science, Springer, New York (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9"},{"key":"7_CR19","doi-asserted-by":"publisher","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: Proceedings 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pp. 143\u2013152. IEEE Computer Society (2010). https:\/\/doi.org\/10.1109\/FOCS.2010.21","DOI":"10.1109\/FOCS.2010.21"},{"issue":"3","key":"7_CR20","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2014","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the Space and Circuit Complexity of Parameterized Problems: classes and Completeness. Algorithmica 71(3), 661\u2013701 (2014). https:\/\/doi.org\/10.1007\/s00453-014-9944-y","journal-title":"Algorithmica"},{"issue":"23","key":"7_CR21","doi-asserted-by":"publisher","first-page":"2513","DOI":"10.1016\/j.tcs.2010.10.043","volume":"412","author":"J Fiala","year":"2011","unstructured":"Fiala, J., Golovach, P.A., Kratochv\u00edl, J.: Parameterized complexity of coloring problems: treewidth versus vertex cover. Theoret. Comput. Sci. 412(23), 2513\u20132523 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2010.10.043","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-662-48054-0_29","volume-title":"Mathematical Foundations of Computer Science 2015","author":"R Ganian","year":"2015","unstructured":"Ganian, R., Kim, E.J., Szeider, S.: Algorithmic applications of tree-cut width. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 348\u2013360. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48054-0_29"},{"key":"7_CR23","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"key":"7_CR24","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.dam.2020.08.013","volume":"287","author":"D Gijswijt","year":"2020","unstructured":"Gijswijt, D., Smit, H., van der Wegen, M.: Computing graph gonality is hard. Discret. Appl. Math. 287, 134\u2013149 (2020). https:\/\/doi.org\/10.1016\/j.dam.2020.08.013","journal-title":"Discret. Appl. Math."},{"key":"7_CR25","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2022.03.021","volume":"918","author":"T Gima","year":"2022","unstructured":"Gima, T., Hanaka, T., Kiyomi, M., Kobayashi, Y., Otachi, Y.: Exploring the gap between treedepth and vertex cover through vertex integrity. Theoret. Comput. Sci. 918, 60\u201376 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.03.021","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR26","unstructured":"Koerkamp, R.G., van der Wegen, M.: Stable gonality is computable. Discrete Math. Theor. Comput. Sci. 21(1), 14 (2019). https:\/\/doi.org\/10.23638\/DMTCS-21-1-10. Paper No. 10"},{"issue":"3","key":"7_CR27","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P Hlin\u011bn\u00fd","year":"2007","unstructured":"Hlin\u011bn\u00fd, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326\u2013362 (2007). https:\/\/doi.org\/10.1093\/comjnl\/bxm052","journal-title":"Comput. J."},{"issue":"4","key":"7_CR28","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/322092.322100","volume":"25","author":"A Itai","year":"1978","unstructured":"Itai, A.: Two-commodity flow. J. ACM 25(4), 596\u2013611 (1978). https:\/\/doi.org\/10.1145\/322092.322100","journal-title":"J. ACM"},{"issue":"1","key":"7_CR29","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jcss.2012.04.004","volume":"79","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1), 39\u201349 (2013). https:\/\/doi.org\/10.1016\/j.jcss.2012.04.004","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/BFb0028825","volume-title":"Fundamentals of Computation Theory","author":"D Seese","year":"1985","unstructured":"Seese, D.: Tree-partite graphs and the complexity of algorithms. In: Budach, L. (ed.) FCT 1985. LNCS, vol. 199, pp. 412\u2013421. Springer, Heidelberg (1985). https:\/\/doi.org\/10.1007\/BFb0028825"},{"key":"7_CR31","unstructured":"Szeider, S.: Not so easy problems for tree decomposable graphs. In: Advances in Discrete Mathematics and Applications: Mysore, 2008. Ramanujan Mathematical Society Lecture Note Series, vol. 13, pp. 179\u2013190. Ramanujan Mathematical Society, Mysore (2010). arXiv:1107.1177"},{"key":"7_CR32","doi-asserted-by":"publisher","unstructured":"Wollan, P.: The structure of graphs not admitting a fixed immersion. J. Comb. Theory Ser. B 110, 47\u201366 (2015). https:\/\/doi.org\/10.1016\/j.jctb.2014.07.003","DOI":"10.1016\/j.jctb.2014.07.003"},{"issue":"5","key":"7_CR33","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1016\/j.ejc.2008.11.010","volume":"30","author":"DR Wood","year":"2009","unstructured":"Wood, D.R.: On tree-partition-width. Eur. J. Combin. 30(5), 1245\u20131253 (2009). https:\/\/doi.org\/10.1016\/j.ejc.2008.11.010","journal-title":"Eur. J. Combin."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15914-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T11:15:35Z","timestamp":1664536535000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15914-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031159138","9783031159145"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15914-5_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 October 2022","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":"T\u00fcbingen","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":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"48","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.inf.uni-tuebingen.de\/wg2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"96","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}