{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:51Z","timestamp":1770921411389,"version":"3.50.1"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-17801-5_32","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:20Z","timestamp":1770918800000},"page":"432-446","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Solution Discovery for\u00a0Vertex Cover, Independent Set, Dominating Set, and\u00a0Feedback Vertex Set"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3953-4339","authenticated-orcid":false,"given":"Rin","family":"Saito","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0006-1366-4377","authenticated-orcid":false,"given":"Anouk","family":"Sommer","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1376-4678","authenticated-orcid":false,"given":"Tatsuhiro","family":"Suga","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0005-8433-3789","authenticated-orcid":false,"given":"Takahiro","family":"Suzuki","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0001-5479-7006","authenticated-orcid":false,"given":"Yuma","family":"Tamura","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"Bergougnoux, B., Kant\u00e9, M.M.: Fast exact algorithms for some connectivity problems parameterized by clique-width. Theoretical Computer Science 782, 30\u201353 (2019), https:\/\/doi.org\/10.1016\/j.tcs.2019.02.030","DOI":"10.1016\/j.tcs.2019.02.030"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"Bertossi, A.A.: Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19(1), 37\u201340 (1984). https:\/\/doi.org\/10.1016\/0020-0190(84)90126-1","DOI":"10.1016\/0020-0190(84)90126-1"},{"key":"32_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2024.105195","volume":"300","author":"HL Bodlaender","year":"2024","unstructured":"Bodlaender, H.L., Groenland, C., Nederlof, J., Swennenhuis, C.: Parameterized problems complete for nondeterministic FPT time and logarithmic space. Inf. Comput. 300, 105195 (2024). https:\/\/doi.org\/10.1016\/j.ic.2024.105195","journal-title":"Inf. Comput."},{"key":"32_CR4","unstructured":"Bousquet, N., Mouawad, A.E., Maaz, S., Nishimura, N., Siebertz, S.: On algorithmic meta-theorems for solution discovery: Tractability and barriers (2025). https:\/\/arxiv.org\/abs\/2510.17344"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Bui-Xuan, B., Such\u00fd, O., Telle, J.A., Vatshelle, M.: Feedback vertex set on graphs of low clique-width. Euro. J. Comb. 34(3), 666\u2013679 (2013). https:\/\/doi.org\/10.1016\/j.ejc.2012.07.023","DOI":"10.1016\/j.ejc.2012.07.023"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1-3), 77\u2013114 (2000). https:\/\/doi.org\/10.1016\/S0166-218X(99)00184-5","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"32_CR7","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":"32_CR8","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248\u2013264 (1972). https:\/\/doi.org\/10.1145\/321694.321699","DOI":"10.1145\/321694.321699"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., et al.: On solution discovery via reconfiguration. In: ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30\u2013October 4, 2023, Krak\u00f3w, Poland - Including 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023). pp. 700\u2013707 (2023). https:\/\/doi.org\/10.3233\/FAIA230334","DOI":"10.3233\/FAIA230334"},{"key":"32_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180\u2013187 (1972). https:\/\/doi.org\/10.1137\/0201013","DOI":"10.1137\/0201013"},{"key":"32_CR12","unstructured":"Grobler, M., et al..: Solution discovery via reconfiguration for problems in P. In: 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8\u201312, 2024, Tallinn, Estonia. pp. 76:1\u201376:20 (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2024.76"},{"key":"32_CR13","unstructured":"Grobler, M., Maaz, S., Mouawad, A.E., Nishimura, N., Ramamoorthi, V., Siebertz, S.: Kernelization complexity of solution discovery problems. In: 35th International Symposium on Algorithms and Computation, ISAAC 2024, December 8\u201311, 2024, Sydney, Australia. pp. 36:1\u201336:17 (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2024.36"},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Sys. Sci. 72(8), 1386\u20131396 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2006.02.001","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"32_CR15","doi-asserted-by":"publisher","unstructured":"van\u00a0den Heuvel, J.: The complexity of change. In: Surveys in Combinatorics 2013, London Mathematical Society Lecture Note Series, vol.\u00a0409, pp. 127\u2013160. Cambridge University Press (2013). https:\/\/doi.org\/10.1017\/CBO9781139506748.005","DOI":"10.1017\/CBO9781139506748.005"},{"key":"32_CR16","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P., Oum, S.: Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38(3), 1012\u20131032 (2008). https:\/\/doi.org\/10.1137\/070685920","DOI":"10.1137\/070685920"},{"key":"32_CR17","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-540-68279-0_8","volume-title":"50 Years of Integer Programming 1958-2008","author":"RM Karp","year":"2010","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems. In: \u00fcnger, M., et al. (eds.) 50 Years of Integer Programming 1958-2008, pp. 219\u2013241. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-540-68279-0_8"},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, N., Philip, G., Ramanujan, M.S., Saurabh, S.: Hardness of $$r$$-dominating set on graphs of diameter $$(r + 1)$$. In: Gutin, G.Z., Szeider, S. (eds.) Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4\u20136, 2013, Revised Selected Papers. Lecture Notes in Computer Science, vol.\u00a08246, pp. 255\u2013267. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_22","DOI":"10.1007\/978-3-319-03898-8_22"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S., Sikdar, S.: FPT algorithms for connected feedback vertex set. J. Combin. Optim. 24(2), 131\u2013146 (2012). https:\/\/doi.org\/10.1007\/s10878-011-9394-2","DOI":"10.1007\/s10878-011-9394-2"},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018). https:\/\/doi.org\/10.3390\/a11040052","DOI":"10.3390\/a11040052"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"Oum, S.: Approximating rank-width and clique-width quickly. ACM Trans. Algorithms 5(1), 10:1\u201310:20 (2008). https:\/\/doi.org\/10.1145\/1435375.1435385","DOI":"10.1145\/1435375.1435385"},{"key":"32_CR22","doi-asserted-by":"crossref","unstructured":"Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Combin. Theory Series B. 96(4), 514\u2013528 (2006). https:\/\/doi.org\/10.1016\/j.jctb.2005.10.006","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.5(2), 266\u2013283 (1976). https:\/\/doi.org\/10.1137\/0205021","DOI":"10.1137\/0205021"},{"key":"32_CR24","unstructured":"Saito, R., Sommer, A., Suga, T., Suzuki, T., Tamura, Y.: Solution discovery for vertex cover, independent set, dominating set, and feedback vertex set (2025). https:\/\/arxiv.org\/abs\/2511.23012"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:24Z","timestamp":1770918804000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}