{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:35Z","timestamp":1771036355806,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,5,26]],"date-time":"2021-05-26T00:00:00Z","timestamp":1621987200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,26]],"date-time":"2021-05-26T00:00:00Z","timestamp":1621987200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"ANR","award":["DEMOGRAPH (ANR-16-CE40-0028)"],"award-info":[{"award-number":["DEMOGRAPH (ANR-16-CE40-0028)"]}]},{"name":"ANR","award":["ESIGMA (ANR-17-CE23-0010)"],"award-info":[{"award-number":["ESIGMA (ANR-17-CE23-0010)"]}]},{"name":"ANR","award":["ELIT (ANR-20-CE48-0008-01)"],"award-info":[{"award-number":["ELIT (ANR-20-CE48-0008-01)"]}]},{"name":"JSPS KAKENHI","award":["JP18K11157"],"award-info":[{"award-number":["JP18K11157"]}]},{"name":"French Embassy in Japan","award":["Program \u201cExploration Japon 2017\u201d"],"award-info":[{"award-number":["Program \u201cExploration Japon 2017\u201d"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s00453-021-00830-x","type":"journal-article","created":{"date-parts":[[2021,5,26]],"date-time":"2021-05-26T12:02:43Z","timestamp":1622030563000},"page":"2351-2373","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings"],"prefix":"10.1007","volume":"83","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8981-9287","authenticated-orcid":false,"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,26]]},"reference":[{"key":"830_CR1","unstructured":"Bergougnoux, B., Kant\u00e9, M.M.: Rank based approach on graphs with structured neighborhood. CoRR, abs\/1805.11275 (2018)"},{"key":"830_CR2","unstructured":"Bergougnoux, B., Kant\u00e9, M.M.: More applications of the $$d$$-neighbor equivalence: connectivity and acyclicity constraints. In: Proc. of the 27th Annual European Symposium on Algorithms (ESA), olume 144 of LIPIcs, pp. 17:1\u201317:14 (2019)"},{"key":"830_CR3","first-page":"81","volume":"15","author":"DM Berman","year":"1997","unstructured":"Berman, D.M., Wang, H., Wargo, L.: Odd induced subgraphs in graphs of maximum degree three. Aust. J. Comb. 15, 81\u201386 (1997)","journal-title":"Aust. J. Comb."},{"issue":"7","key":"830_CR4","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1016\/j.dam.2009.09.009","volume":"158","author":"B Bui-Xuan","year":"2010","unstructured":"Bui-Xuan, B., Telle, J.A., Vatshelle, M.: $$H$$-join decomposable graphs and algorithms with runtime single exponential in rankwidth. Discrete Appl. Math. 158(7), 809\u2013819 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"39","key":"830_CR5","doi-asserted-by":"publisher","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","volume":"412","author":"B Bui-Xuan","year":"2011","unstructured":"Bui-Xuan, B., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theoret. Comput. Sci. 412(39), 5187\u20135204 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"830_CR6","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2013.01.009","volume":"511","author":"B Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoret. Comput. Sci. 511, 66\u201376 (2013)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"830_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.jda.2011.03.004","volume":"9","author":"L Cai","year":"2011","unstructured":"Cai, L., Yang, B.: Parameterized complexity of even\/odd subgraph problems. J. Discrete Algorithms 9(3), 231\u2013240 (2011)","journal-title":"J. Discrete Algorithms"},{"issue":"1\u20133","key":"830_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0012-365X(92)00563-7","volume":"132","author":"Y Caro","year":"1994","unstructured":"Caro, Y.: On induced subgraphs with odd degrees. Discrete Math. 132(1\u20133), 23\u201328 (1994)","journal-title":"Discrete Math."},{"key":"830_CR9","first-page":"65","volume":"44","author":"Y Caro","year":"2003","unstructured":"Caro, Y., Klostermeyer, W.: The odd domination number of a graph. J. Comb. Math. Comb. Comput. 44, 65\u201384 (2003)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"3","key":"830_CR10","doi-asserted-by":"publisher","first-page":"225","DOI":"10.7151\/dmgt.1276","volume":"25","author":"Y Caro","year":"2005","unstructured":"Caro, Y., Klostermeyer, W., Yuster, R.: Connected odd dominating sets in graphs. Discuss. Math. Graph Theory 25(3), 225\u2013239 (2005)","journal-title":"Discuss. Math. Graph Theory"},{"key":"830_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"1","key":"830_CR12","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00453-012-9667-x","volume":"68","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M., Schlotter, I.: Parameterized complexity of Eulerian deletion problems. Algorithmica 68(1), 41\u201361 (2014)","journal-title":"Algorithmica"},{"key":"830_CR13","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"830_CR14","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer, Berlin (2013)"},{"issue":"2","key":"830_CR15","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/S0097539797323571","volume":"29","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R., Vardy, A., Whittle, G.: The parametrized complexity of some fundamental problems in coding theory. SIAM J. Comput. 29(2), 545\u2013570 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"830_CR16","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F.A., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143\u2013153 (2011)","journal-title":"Inf. Comput."},{"key":"830_CR17","series-title":"Texts in Theoretical Computer Science","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science, Springer, Berlin (2006)"},{"issue":"5","key":"830_CR18","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941\u20131956 (2010)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"830_CR19","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1137\/130910932","volume":"43","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput. 43(5), 1541\u20131563 (2014)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"830_CR20","first-page":"9:1","volume":"15","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms 15(1), 9:1-9:27 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"830_CR21","doi-asserted-by":"crossref","unstructured":"Frank, A., Jord\u00e1n, T., Szigeti, Z.: An orientation theorem with parity conditions. In: Proc. of the 7th International Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 1610 of LNCS, pp. 183\u2013190 (1999)","DOI":"10.1007\/3-540-48777-8_14"},{"issue":"1","key":"830_CR22","first-page":"59","volume":"123","author":"R Ganian","year":"2013","unstructured":"Ganian, R., Hlinen\u00fd, P., Obdrz\u00e1lek, J.: Better algorithms for satisfiability problems for formulas of bounded rank-width. Fundam. Inf. 123(1), 59\u201376 (2013)","journal-title":"Fundam. Inf."},{"issue":"3","key":"830_CR23","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1016\/j.ejc.2012.07.024","volume":"34","author":"R Ganian","year":"2013","unstructured":"Ganian, R., Hlinen\u00fd, P., Obdrz\u00e1lek, J.: A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width. Eur. J. Comb. 34(3), 680\u2013701 (2013)","journal-title":"Eur. J. Comb."},{"key":"830_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2018.03.001","volume":"97","author":"P Goyal","year":"2018","unstructured":"Goyal, P., Misra, P., Panolan, F., Philip, G., Saurabh, S.: Finding even subgraphs even faster. J. Comput. Syst. Sci. 97, 1\u201313 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"830_CR25","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.tcs.2015.05.038","volume":"598","author":"S Gravier","year":"2015","unstructured":"Gravier, S., Javelle, J., Mhalla, M., Perdrix, S.: On weak odd domination and graph-based quantum secret sharing. Theoret. Comput. Sci. 598, 129\u2013137 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"830_CR26","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1142\/S0129054100000272","volume":"11","author":"MM Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M., Kratochv\u00edl, J., Telle, J.A.: Mod-2 independence and domination in graphs. Int. J. Found. Comput. Sci. 11(3), 355\u2013363 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"830_CR27","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s00373-018-1892-x","volume":"34","author":"X Hou","year":"2018","unstructured":"Hou, X., Yu, L., Li, J., Liu, B.: Odd induced subgraphs in graphs with treewidth at most two. Graphs Comb. 34(4), 535\u2013544 (2018)","journal-title":"Graphs Comb."},{"issue":"2","key":"830_CR28","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"830_CR29","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"830_CR30","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth. Computations and Approximations. Springer-Verlag LNCS (1994)","DOI":"10.1007\/BFb0045375"},{"issue":"2","key":"830_CR31","first-page":"13:1","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), 13:1-13:30 (2018)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"830_CR32","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/16M1104834","volume":"47","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. SIAM J. Comput. 47(3), 675\u2013702 (2018)","journal-title":"SIAM J. Comput."},{"key":"830_CR33","volume-title":"Combinatorial Problems and Exercises","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: Combinatorial Problems and Exercises. North-Holland, Amsterdam (1979)"},{"key":"830_CR34","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"830_CR35","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.dam.2016.08.006","volume":"231","author":"S Oum","year":"2017","unstructured":"Oum, S.: Rank-width: algorithmic and structural results. Discrete Appl. Math. 231, 15\u201324 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"830_CR36","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Comb. Theory Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"key":"830_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2013.10.030","volume":"167","author":"S Porschen","year":"2014","unstructured":"Porschen, S., Schmidt, T., Speckenmeyer, E., Wotzlaw, A.: XSAT and NAE-SAT of linear CNF classes. Discrete Appl. Math. 167, 1\u201314 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"830_CR38","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0012-365X(93)E0186-8","volume":"140","author":"AJ Radcliffe","year":"1995","unstructured":"Radcliffe, A.J., Scott, A.D.: Every tree contains a large induced subgraph with all degrees odd. Discrete Math. 140(1\u20133), 275\u2013279 (1995)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"830_CR39","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.tcs.2007.03.043","volume":"377","author":"M Rao","year":"2007","unstructured":"Rao, M.: MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theoret. Comput. Sci. 377(1\u20133), 260\u2013267 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"830_CR40","unstructured":"R\u00f6ysk\u00f6, A.: https:\/\/cstheory.stackexchange.com\/questions\/45885\/complexity-of-finding-the-largest-induced-subgraph-with-all-even-degrees"},{"key":"830_CR41","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1017\/S0963548300000389","volume":"1","author":"AD Scott","year":"1992","unstructured":"Scott, A.D.: Large induced subgraphs with all degrees odd. Comb. Probab. Comput. 1, 335\u2013349 (1992)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"830_CR42","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s003730170028","volume":"17","author":"AD Scott","year":"2001","unstructured":"Scott, A.D.: On induced subgraphs with all degrees odd. Graphs Comb. 17(3), 539\u2013553 (2001)","journal-title":"Graphs Comb."},{"key":"830_CR43","unstructured":"Sutner, K.: Additive automata on graphs. Complex Systems 2(6), (1988)"},{"issue":"6","key":"830_CR44","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.641542","volume":"43","author":"A Vardy","year":"1997","unstructured":"Vardy, A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inf. Theory 43(6), 1757\u20131766 (1997)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00830-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00830-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00830-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T14:04:49Z","timestamp":1626962689000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00830-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,26]]},"references-count":44,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["830"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00830-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,26]]},"assertion":[{"value":"18 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}