{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:40Z","timestamp":1770994060891,"version":"3.50.1"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643684369","type":"print"},{"value":"9781643684376","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T00:00:00Z","timestamp":1695859200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,28]]},"abstract":"<jats:p>The dynamics of real-world applications and systems require efficient methods for improving infeasible solutions or restoring corrupted ones by making modifications to the current state of a system in a restricted way. We propose a new framework of solution discovery via reconfiguration for constructing a feasible solution for a given problem by executing a sequence of small modifications starting from a given state. Our framework integrates different aspects of classical local search, reoptimization, and combinatorial reconfiguration. We exemplify our framework on a multitude of fundamental combinatorial problems, namely VERTEX COVER, INDEPENDENT SET, DOMINATING SET, and COLORING. We study the classical as well as the parameterized complexity of the solution discovery variants of those problems and explore the boundary between tractable and intractable instances.<\/jats:p>","DOI":"10.3233\/faia230334","type":"book-chapter","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:08:40Z","timestamp":1695978520000},"source":"Crossref","is-referenced-by-count":2,"title":["On Solution Discovery via Reconfiguration"],"prefix":"10.3233","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6148-9212","authenticated-orcid":false,"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8103-6440","authenticated-orcid":false,"given":"Mario","family":"Grobler","sequence":"additional","affiliation":[{"name":"University of Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3531-7644","authenticated-orcid":false,"given":"Nicole","family":"Megow","sequence":"additional","affiliation":[{"name":"University of Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2481-4968","authenticated-orcid":false,"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[{"name":"American University of Beirut, Lebanon"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8554-6392","authenticated-orcid":false,"given":"Vijayaragunathan","family":"Ramamoorthi","sequence":"additional","affiliation":[{"name":"University of Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5097-9929","authenticated-orcid":false,"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7776-3426","authenticated-orcid":false,"given":"Daniel","family":"Schmand","sequence":"additional","affiliation":[{"name":"University of Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6347-1198","authenticated-orcid":false,"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"University of Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2023"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA230334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:08:42Z","timestamp":1695978522000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA230334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,28]]},"ISBN":["9781643684369","9781643684376"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia230334","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,28]]}}}