{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T21:30:32Z","timestamp":1769290232353,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T00:00:00Z","timestamp":1761868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T00:00:00Z","timestamp":1761868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H05964,JP22H03549"],"award-info":[{"award-number":["JP20H05964,JP22H03549"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00224-025-10249-4","type":"journal-article","created":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T04:56:16Z","timestamp":1761886576000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Pre-assignment Problem for Unique Minimum Vertex Cover on Bipartite Graphs"],"prefix":"10.1007","volume":"69","author":[{"given":"Takashi","family":"Horiyama","sequence":"first","affiliation":[]},{"given":"Kazuhisa","family":"Seto","sequence":"additional","affiliation":[]},{"given":"Ryu","family":"Suzuki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,10,31]]},"reference":[{"key":"10249_CR1","first-page":"147","volume":"30","author":"P Afshani","year":"2004","unstructured":"Afshani, P., Hatami, H., Mahmoodian, E.S.: On the spectrum of the forced matching number of graphs. Australas. J. Comb. 30, 147\u2013160 (2004)","journal-title":"Australas. J. Comb."},{"issue":"25","key":"10249_CR2","doi-asserted-by":"publisher","first-page":"26886","DOI":"10.1609\/aaai.v39i25.3489","volume":"39","author":"S An","year":"2025","unstructured":"An, S., Chang, Y., Cho, K., Kwon, O., Lee, M., Oh, E., Shin, H.: Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs. Proceedings of the AAAI Conference on Artificial Intelligence 39(25), 26886\u201326894 (2025). https:\/\/doi.org\/10.1609\/aaai.v39i25.3489","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"10249_CR3","doi-asserted-by":"publisher","unstructured":"Armada, C.L., Canoy, S.R., Jr.: Forcing independent domination number of a graph. Eur. J. Pure Appl. Math. 12(4), 1371\u20131381 (2019). https:\/\/doi.org\/10.29020\/nybg.ejpam.v12i4.3484","DOI":"10.29020\/nybg.ejpam.v12i4.3484"},{"key":"10249_CR4","doi-asserted-by":"publisher","unstructured":"Bruy\u00e8re, V., M\u00e9lot, H.: Tur\u00e1n graphs, stability number, and fibonacci index. In: Yang, B., Du, D.Z., Wang, C.A. (eds.) Combinatorial Optimization and Applications. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 127\u2013138 (2008). https:\/\/doi.org\/10.1007\/978-3-540-85097-7_12","DOI":"10.1007\/978-3-540-85097-7_12"},{"issue":"20","key":"10249_CR5","doi-asserted-by":"publisher","first-page":"3987","DOI":"10.1016\/0040-4020(84)85077-2","volume":"40","author":"C Herndon W","year":"1984","unstructured":"Herndon W, C., Hosoya, H.: Parameterized valence bond calculations for benzenoid hydrocarbons using clar structure. Tetrahedron 40(20), 3987\u20133995 (1984). https:\/\/doi.org\/10.1016\/0040-4020(84)85077-2","journal-title":"Tetrahedron"},{"key":"10249_CR6","first-page":"161","volume":"25","author":"G Chartrand","year":"1997","unstructured":"Chartrand, G., Gavlas, H., Vandell, R.C.: The forcing domination number of a graph. J. Comb. Math. Comb. Comput. 25, 161\u2013174 (1997)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"10249_CR7","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.disc.2013.10.011","volume":"315\u2013316","author":"J Cooper","year":"2014","unstructured":"Cooper, J., Kirkpatrick, A.: Critical sets for sudoku and general graph colorings. Discret. Math. 315\u2013316, 112\u2013119 (2014). https:\/\/doi.org\/10.1016\/j.disc.2013.10.011","journal-title":"Discret. Math."},{"key":"10249_CR8","first-page":"33","volume":"12","author":"J Cooper","year":"1994","unstructured":"Cooper, J., Donovan, D., Seberry, J.: Secret sharing schemes arising from Latin squares. Bull. Inst. Combin. Appl. 12, 33\u201343 (1994)","journal-title":"Bull. Inst. Combin. Appl."},{"key":"10249_CR9","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2018.01.020","volume":"748","author":"ED Demaine","year":"2018","unstructured":"Demaine, E.D., Ma, F., Schvartzman, A., Waingarten, E., Aaronson, S.: The fewest clues problem. Theoret. Comput. Sci. 748, 28\u201339 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.01.020","journal-title":"Theoret. Comput. Sci."},{"key":"10249_CR10","doi-asserted-by":"publisher","unstructured":"Diestel, R.: Graph Theory, 4th Edition. Graduate texts in mathematics, vol. 173. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-662-53622-3","DOI":"10.1007\/978-3-662-53622-3"},{"key":"10249_CR11","doi-asserted-by":"publisher","first-page":"517","DOI":"10.4153\/CJM-1958-052-0","volume":"10","author":"AL Dulmage","year":"1958","unstructured":"Dulmage, A.L., Mendelsohn, N.S.: Coverings of bipartite graphs. Can. J. Math. 10, 517\u2013534 (1958). https:\/\/doi.org\/10.4153\/CJM-1958-052-0","journal-title":"Can. J. Math."},{"key":"10249_CR12","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965). https:\/\/doi.org\/10.4153\/CJM-1965-045-4","journal-title":"Can. J. Math."},{"issue":"3","key":"10249_CR13","first-page":"401","volume":"9","author":"T Gallai","year":"1964","unstructured":"Gallai, T.: Maximale systeme unabh\u00e4ngiger kanten. A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei 9(3), 401\u2013413 (1964)","journal-title":"A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei"},{"key":"10249_CR14","unstructured":"Goergen, K., Fernau, H., Oest, E., Wolf, P.: All paths lead to Rome. (2022). https:\/\/arxiv.org\/abs\/2207.09439"},{"issue":"1","key":"10249_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1017\/S0004972700017883","volume":"41","author":"K Gray","year":"1990","unstructured":"Gray, K.: On the minimum number of blocks defining a design. Bull. Aust. Math. Soc. 41(1), 97\u2013112 (1990). https:\/\/doi.org\/10.1017\/S0004972700017883","journal-title":"Bull. Aust. Math. Soc."},{"issue":"1","key":"10249_CR16","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01192587","volume":"6","author":"F Harary","year":"1991","unstructured":"Harary, F., Klein, D.J., \u017divkovi\u010d, T.P.: Graphical properties of polyhexes: Perfect matching vector and forcing. J. Math. Chem. 6(1), 295\u2013306 (1991). https:\/\/doi.org\/10.1007\/BF01192587","journal-title":"J. Math. Chem."},{"issue":"1","key":"10249_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/050641594","volume":"37","author":"F Harary","year":"2007","unstructured":"Harary, F., Slany, W., Verbitsky, O.: On the computational complexity of the forcing chromatic number. SIAM J. Comput. 37(1), 1\u201319 (2007). https:\/\/doi.org\/10.1137\/050641594","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10249_CR18","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.dam.2005.03.004","volume":"149","author":"H Hatami","year":"2005","unstructured":"Hatami, H., Maserrat, H.: On the computational complexity of defining sets. Discret. Appl. Math. 149(1), 101\u2013110 (2005). https:\/\/doi.org\/10.1016\/j.dam.2005.03.004","journal-title":"Discret. Appl. Math."},{"issue":"11","key":"10249_CR19","doi-asserted-by":"publisher","first-page":"1490","DOI":"10.1587\/transfun.E102.A.1490","volume":"E102.A","author":"Y Higuchi","year":"2019","unstructured":"Higuchi, Y., Kimura, K.: NP-completeness of Fill-a-Pix and $$\\Sigma _2^P$$-completeness of its fewest clues problem. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E102.A(11), 1490\u20131496 (2019). https:\/\/doi.org\/10.1587\/transfun.E102.A.1490","journal-title":"IEICE Trans. Fund. Electron. Commun. Comput. Sci."},{"issue":"4","key":"10249_CR20","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973). https:\/\/doi.org\/10.1137\/0202019","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10249_CR21","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0012-365X(85)90177-3","volume":"57","author":"G Hopkins","year":"1985","unstructured":"Hopkins, G., Staton, W.: Graphs with unique maximum independent sets. Discret. Math. 57(3), 245\u2013251 (1985). https:\/\/doi.org\/10.1016\/0012-365X(85)90177-3","journal-title":"Discret. Math."},{"key":"10249_CR22","doi-asserted-by":"publisher","unstructured":"Horiyama, T., Kobayashi, Y., Ono, H., Kazuhisa, S., Ryu, S.: Theoretical aspects of generating instances with unique solutions: Pre-assignment models for unique vertex cover. Proceedings of the AAAI Conference on Artificial Intelligence 38(18), 20726\u201320734 (2024). https:\/\/doi.org\/10.1609\/aaai.v38i18.30060","DOI":"10.1609\/aaai.v38i18.30060"},{"key":"10249_CR23","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems. Springer US, Boston, MA, pp. 85\u2013103 (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"10249_CR24","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1002\/jcc.540080432","volume":"8","author":"DJ Klein","year":"1987","unstructured":"Klein, D.J., Randi\u0107, M.: Innate degree of freedom of a graph. J. Comput. Chem. 8(4), 516\u2013521 (1987). https:\/\/doi.org\/10.1002\/jcc.540080432","journal-title":"J. Comput. Chem."},{"issue":"4","key":"10249_CR25","doi-asserted-by":"publisher","first-page":"469","DOI":"10.5562\/cca2295","volume":"86","author":"C Larson","year":"2013","unstructured":"Larson, C., Cleemput, N.V.: Forcing independence. Croatia Chem. Acta 86(4), 469\u2013475 (2013). https:\/\/doi.org\/10.5562\/cca2295","journal-title":"Croatia Chem. Acta"},{"key":"10249_CR26","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. AMS Chelsea Publishing, Providence, Rhode Island (1986)"},{"key":"10249_CR27","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1134\/S1990478920020131","volume":"14","author":"YA Loverov","year":"2020","unstructured":"Loverov, Y.A., Orlovich, Y.L.: NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs. J. Appl. Ind. Math. 14, 353\u2013368 (2020). https:\/\/doi.org\/10.1134\/S1990478920020131","journal-title":"J. Appl. Ind. Math."},{"issue":"1","key":"10249_CR28","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0378-3758(98)00053-6","volume":"73","author":"ES Mahmoodian","year":"1998","unstructured":"Mahmoodian, E.S.: Defining sets and uniqueness in graph colorings: A survey. J. Stat. Plann. Infer. 73(1), 85\u201389 (1998). https:\/\/doi.org\/10.1016\/S0378-3758(98)00053-6","journal-title":"J. Stat. Plann. Infer."},{"issue":"1","key":"10249_CR29","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF00551410","volume":"55","author":"RE Merrifield","year":"1980","unstructured":"Merrifield, R.E., Simmons, H.E.: The structures of molecular topological spaces. Theor. Chim. Acta 55(1), 55\u201375 (1980). https:\/\/doi.org\/10.1007\/BF00551410","journal-title":"Theor. Chim. Acta"},{"key":"10249_CR30","doi-asserted-by":"publisher","unstructured":"Murota, K.: Matrices and Matroids for Systems Analysis, 1st edn. Springer, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-03994-2","DOI":"10.1007\/978-3-642-03994-2"},{"issue":"5","key":"10249_CR31","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1016\/j.dam.2007.07.019","volume":"156","author":"R Pepper","year":"2008","unstructured":"Pepper, R.: An upper bound on the independence number of benzenoid systems. Discret. Appl. Math. 156(5), 607\u2013619 (2008). https:\/\/doi.org\/10.1016\/j.dam.2007.07.019","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"10249_CR32","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"SP Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31(2), 398\u2013427 (2001). https:\/\/doi.org\/10.1137\/S0097539797321602","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10249_CR33","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s10910-006-9133-6","volume":"42","author":"D Vuki\u011bevi\u0107","year":"2007","unstructured":"Vuki\u011bevi\u0107, D., Trinajsti\u0107, N.: On the anti-forcing number of benzenoids. J. Math. Chem. 42(3), 575\u2013583 (2007). https:\/\/doi.org\/10.1007\/s10910-006-9133-6","journal-title":"J. Math. Chem."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10249-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10249-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10249-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T08:52:46Z","timestamp":1769244766000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10249-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,31]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10249"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10249-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,31]]},"assertion":[{"value":"25 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"35"}}