{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T17:11:07Z","timestamp":1784308267228,"version":"3.55.0"},"reference-count":47,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100010446","name":"Institute for Basic Science","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100010446","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,9]]},"DOI":"10.1016\/j.tcs.2026.116173","type":"journal-article","created":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T15:18:36Z","timestamp":1784042316000},"page":"116173","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs"],"prefix":"10.1016","volume":"1084","author":[{"given":"Shinwoo","family":"An","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yeonsu","family":"Chang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kyungjin","family":"Cho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1820-1962","authenticated-orcid":false,"given":"O-joung","family":"Kwon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Myounghwan","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eunjin","family":"Oh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hyeonjun","family":"Shin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"25","key":"10.1016\/j.tcs.2026.116173_bib0001","first-page":"26886","article-title":"Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs","volume":"39","author":"An","year":"2025","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"issue":"4","key":"10.1016\/j.tcs.2026.116173_bib0002","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"TSPLIB\u2014a traveling salesman problem library","volume":"3","author":"Reinelt","year":"1991","journal-title":"ORSA J. Comput."},{"key":"10.1016\/j.tcs.2026.116173_bib0003","unstructured":"M. Kelly, R. Longjohn, K. Nottingham, The UCI machine learning repository, 2007. https:\/\/archive.ics.uci.edu."},{"key":"10.1016\/j.tcs.2026.116173_bib0004","first-page":"283","article-title":"SATLIB: an online resource for research on SAT","volume":"2000","author":"Hoos","year":"2000","journal-title":"Sat"},{"key":"10.1016\/j.tcs.2026.116173_bib0005","series-title":"Advances in Graph Theory","first-page":"259","article-title":"Hamiltonian cycles and uniquely edge colourable graphs","volume":"Vol. 3","author":"Thomason","year":"1978"},{"key":"10.1016\/j.tcs.2026.116173_bib0006","series-title":"Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing","first-page":"70","article-title":"Unique maximum matching algorithms","author":"Gabow","year":"1999"},{"key":"10.1016\/j.tcs.2026.116173_bib0007","series-title":"32nd Computational Complexity Conference (CCC 2017)","article-title":"PPSZ for general k-SAT-making Hertli\u2019s analysis simpler and 3-SAT faster","author":"Scheder","year":"2017"},{"issue":"2","key":"10.1016\/j.tcs.2026.116173_bib0008","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/120868177","article-title":"3-SAT faster and simpler\u2014unique-SAT bounds for PPSZ hold in general","volume":"43","author":"Hertli","year":"2014","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.tcs.2026.116173_bib0009","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1016\/j.jcss.2007.06.015","article-title":"The complexity of unique k-SAT: an isolation lemma for k-CNFs","volume":"74","author":"Calabro","year":"2008","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.tcs.2026.116173_bib0010","series-title":"International Colloquium on Automata, Languages, and Programming","first-page":"600","article-title":"Breaking the PPSZ barrier for unique 3-SAT","author":"Hertli","year":"2014"},{"issue":"1","key":"10.1016\/j.tcs.2026.116173_bib0011","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/050641594","article-title":"On the computational complexity of the forcing chromatic number","volume":"37","author":"Harary","year":"2007","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.116173_bib0012","first-page":"161","article-title":"The forcing domination number of a graph","volume":"25","author":"Chartrand","year":"1997","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"10.1016\/j.tcs.2026.116173_bib0013","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1007\/s10878-018-0330-6","article-title":"Restricted power domination and zero forcing problems","volume":"37","author":"Bozeman","year":"2019","journal-title":"J. Comb. Optim."},{"issue":"6","key":"10.1016\/j.tcs.2026.116173_bib0014","doi-asserted-by":"crossref","first-page":"1789","DOI":"10.1016\/j.disc.2017.10.031","article-title":"The relationship between k-forcing and k-power domination","volume":"341","author":"Ferrero","year":"2018","journal-title":"Discrete Math."},{"key":"10.1016\/j.tcs.2026.116173_bib0015","series-title":"Proceedings of the AAAI Conference on Artificial Intelligence","first-page":"20726","article-title":"Theoretical aspects of generating instances with unique solutions: pre-assignment models for unique vertex cover","volume":"vol. 38","author":"Horiyama","year":"2024"},{"key":"10.1016\/j.tcs.2026.116173_bib0016","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2018.01.020","article-title":"The fewest clues problem","volume":"748","author":"Demaine","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.116173_bib0017","series-title":"9th International Conference on Fun with Algorithms (FUN 2018)","first-page":"25:1","article-title":"The fewest clues problem of picross 3D","volume":"vol. 100","author":"Kimura","year":"2018"},{"key":"10.1016\/j.tcs.2026.116173_bib0018","doi-asserted-by":"crossref","DOI":"10.1016\/j.orl.2024.107105","article-title":"How many clues to give? A bilevel formulation for the minimum Sudoku clue problem","volume":"54","author":"Tjusila","year":"2024","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"10.1016\/j.tcs.2026.116173_bib0019","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s00224-025-10249-4","article-title":"The complexity of pre-assignment problem for unique minimum vertex cover on bipartite graphs","volume":"69","author":"Horiyama","year":"2025","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"10.1016\/j.tcs.2026.116173_bib0020","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","article-title":"Upper bounds to the clique width of graphs","volume":"101","author":"Courcelle","year":"2000","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"10.1016\/j.tcs.2026.116173_bib0021","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","article-title":"Graph minors. XX. Wagner\u2019s conjecture","volume":"92","author":"Robertson","year":"2004","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"10.1016\/j.tcs.2026.116173_bib0022","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The monadic second-order logic of graphs. I. Recognizable sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inf. Comput."},{"issue":"4","key":"10.1016\/j.tcs.2026.116173_bib0023","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1137\/S0097539701385351","article-title":"On the relationship between clique-width and treewidth","volume":"34","author":"Corneil","year":"2005","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/j.tcs.2026.116173_bib0024","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","article-title":"Linear time solvable optimization problems on graphs of bounded clique-width","volume":"33","author":"Courcelle","year":"2000","journal-title":"Theory Comput. Syst."},{"issue":"2-3","key":"10.1016\/j.tcs.2026.116173_bib0025","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","article-title":"Edge dominating set and colorings on graphs with fixed clique-width","volume":"126","author":"Kobler","year":"2003","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"10.1016\/j.tcs.2026.116173_bib0026","doi-asserted-by":"crossref","first-page":"1941","DOI":"10.1137\/080742270","article-title":"Intractability of clique-width parameterizations","volume":"39","author":"Fomin","year":"2010","journal-title":"SIAM J. Comput."},{"issue":"5","key":"10.1016\/j.tcs.2026.116173_bib0027","doi-asserted-by":"crossref","first-page":"1541","DOI":"10.1137\/130910932","article-title":"Almost optimal lower bounds for problems parameterized by clique-width","volume":"43","author":"Fomin","year":"2014","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.tcs.2026.116173_bib0028","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/3280824","article-title":"Clique-width III: Hamiltonian cycle and the odd case of graph coloring","volume":"15","author":"Fomin","year":"2019","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"10.1016\/j.tcs.2026.116173_bib0029","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1007\/s00453-019-00663-9","article-title":"An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width","volume":"82","author":"Bergougnoux","year":"2020","journal-title":"Algorithmica"},{"issue":"03","key":"10.1016\/j.tcs.2026.116173_bib0030","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1142\/S0129054199000241","article-title":"On the clique-width of graph with few P4\u2019s","volume":"10","author":"Makowsky","year":"1999","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.116173_bib0031","series-title":"On the clique-width of some perfect graph classes","first-page":"423","volume":"vol. 11","author":"Golumbic","year":"2000"},{"issue":"2","key":"10.1016\/j.tcs.2026.116173_bib0032","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","article-title":"Simple linear time recognition of unit interval graphs","volume":"55","author":"Corneil","year":"1995","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10.1016\/j.tcs.2026.116173_bib0033","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/S0097539700372216","article-title":"A fully dynamic algorithm for recognizing and representing proper interval graphs","volume":"31","author":"Hell","year":"2001","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.tcs.2026.116173_bib0034","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","article-title":"Dominating sets for split and bipartite graphs","volume":"19","author":"Bertossi","year":"1984","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10.1016\/j.tcs.2026.116173_bib0035","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","article-title":"k-NLC graphs and polynomial algorithms","volume":"54","author":"Wanke","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.116173_bib0036","series-title":"Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1998)","first-page":"39","article-title":"Clique-decomposition, NLC-decomposition, and modular decomposition\u2014relationships and results for random graphs","volume":"vol. 132","author":"Johansson","year":"1998"},{"key":"10.1016\/j.tcs.2026.116173_bib0037","series-title":"STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing","first-page":"354","article-title":"Clique-width minimization is NP-hard (Extended abstract)","author":"Fellows","year":"2006"},{"issue":"4","key":"10.1016\/j.tcs.2026.116173_bib0038","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","article-title":"Approximating clique-width and branch-width","volume":"96","author":"Oum","year":"2006","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"10.1016\/j.tcs.2026.116173_bib0039","first-page":"10","article-title":"Approximating rank-width and clique-width quickly","volume":"5","author":"Oum","year":"2009","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"10.1016\/j.tcs.2026.116173_bib0040","doi-asserted-by":"crossref","first-page":"1085","DOI":"10.1137\/22M153937X","article-title":"Fast FPT-approximation of branchwidth","volume":"53","author":"Fomin","year":"2024","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.116173_bib0041","series-title":"STOC\u201924\u2014Proceedings of the 56th Annual ACM Symposium on Theory of Computing","first-page":"1538","article-title":"Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth","author":"Korhonen","year":"2024"},{"key":"10.1016\/j.tcs.2026.116173_bib0042","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid method and its consequences in combinatorial optimization","volume":"1","author":"Gr\u00f6tschel","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/j.tcs.2026.116173_bib0043","series-title":"43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)","article-title":"Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth","author":"Marx","year":"2016"},{"key":"10.1016\/j.tcs.2026.116173_bib0044","series-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"262","article-title":"Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth","author":"Golovach","year":"2018"},{"key":"10.1016\/j.tcs.2026.116173_bib0045","series-title":"51st International Colloquium on Automata, Languages, and Programming","first-page":"66","article-title":"Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover","volume":"Vol. 297","author":"Foucaud","year":"2024"},{"key":"10.1016\/j.tcs.2026.116173_bib0046","series-title":"Theory and Applications of Models of Computation","first-page":"124","article-title":"Tight double exponential lower bounds","volume":"Vol. 14637","author":"Bliznets","year":"2024"},{"issue":"4","key":"10.1016\/j.tcs.2026.116173_bib0047","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","article-title":"On approximating the minimum independent dominating set","volume":"37","author":"Irving","year":"1991","journal-title":"Inf. Process. Lett."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526004020?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526004020?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T17:01:41Z","timestamp":1784307701000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526004020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9]]},"references-count":47,"alternative-id":["S0304397526004020"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.116173","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.116173","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"116173"}}