{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:22:21Z","timestamp":1737091341057,"version":"3.33.0"},"reference-count":28,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3603,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1997,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the definability in monadic \u2211<jats:sub>1<\/jats:sub><jats:sup>1<\/jats:sup>and monadic \u03a0<jats:sub>1<\/jats:sub><jats:sup>1<\/jats:sup>of the problems REG<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>, of whether there is a regular subgraph of degree<jats:italic>k<\/jats:italic>in some given graph, and XREG<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>, of whether, for a given rooted graph, there is a regular subgraph of degree<jats:italic>k<\/jats:italic>in which the root has degree<jats:italic>k<\/jats:italic>, and their restrictions to graphs in which every vertex has degree at most<jats:italic>k<\/jats:italic>, namely REG<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>and XREG<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>, respectively, for<jats:italic>k<\/jats:italic>\u2265 2 (all our graphs are undirected). Our motivation partly stems from the fact (which we prove here) that REG<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>and XREG<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>are logspace equivalent to CONN and REACH, respectively, for<jats:italic>k<\/jats:italic>\u2265 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first \u2010 order reductions, monadic \u2211<jats:sub>1<\/jats:sub><jats:sup>1<\/jats:sup>games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic \u2211<jats:sub>1<\/jats:sub><jats:sup>1<\/jats:sup>and monadic \u03a0<jats:sub>1<\/jats:sub><jats:sup>1<\/jats:sup>, and we compare the definability of these problems (in monadic \u2211<jats:sub>1<\/jats:sub><jats:sup>1<\/jats:sup>and monadic \u03a0<jats:sub>1<\/jats:sub><jats:sup>1<\/jats:sup>with their computational complexity (which varies from solvable using logspace to NP \u2010 complete).<\/jats:p>","DOI":"10.1002\/malq.19970430102","type":"journal-article","created":{"date-parts":[[2007,5,30]],"date-time":"2007-05-30T15:25:49Z","timestamp":1180538749000},"page":"1-21","source":"Crossref","is-referenced-by-count":1,"title":["Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second \u2010 Order Logic"],"prefix":"10.1002","volume":"43","author":[{"given":"Iain A.","family":"Stewart","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.2307\/2274958"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56503-5_19"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"Cosmadakis S. S. Logical reducibility and monadic NP. In: Proc. 34th IEEE Ann. Symp. on Foundations of Computer Science1993 pp.52\u201361.","DOI":"10.1109\/SFCS.1993.366882"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13331-3_51"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/5.2.213"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"e_1_2_1_8_2","series-title":"SIAM \u2010 AMS Proceedings Vol. 7","first-page":"43","volume-title":"Complexity of Computation","author":"Fagin R.","year":"1974"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210112"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90218-I"},{"journal-title":"Inform. and Comput.","article-title":"On monadic NP versus monadic co \u2010 NP","author":"Fagin R.","key":"e_1_2_1_11_2"},{"key":"e_1_2_1_12_2","first-page":"35","article-title":"Sur quelques classifications des syst\u00e8ms de relations","volume":"1","author":"Fra\u00efss\u00e9 R.","year":"1954","journal-title":"Publ. Sci. Univ. Alger."},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP \u2010 Completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_1_13_2"},{"key":"e_1_2_1_14_2","first-page":"1","volume-title":"Trends in Theoretical Computer Science","author":"Gurevich Y.","year":"1988"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211050"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90039-8"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"Immerman N. Expressibility as a complexity measure: Results and directions. In: Proc. 2nd IEEE Ann. Symp. on Structure in Complexity Theory1987 pp.194\u2013202.","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90058-5"},{"volume-title":"Handbook of Logic in Computer Science","year":"1992","author":"Makowsky J. A.","key":"e_1_2_1_20_2"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19870330107"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","unstructured":"Schwentick T. Graph connectivity and monadic NP. In: Proc. 35th IEEE Ann. Symp. on Foundations of Computer Science1994 pp.614\u2013622.","DOI":"10.1109\/SFCS.1994.365730"},{"key":"e_1_2_1_23_2","unstructured":"Schwentick T. On Winning Ehrenfeucht Games and Monadic NP. Ph.D. Thesis Johannes Gutenberg \u2010 Universit\u00e4t Mainz Tech. Rep. Nr. 3\/95."},{"key":"e_1_2_1_24_2","first-page":"65","article-title":"Logical characterizations of bounded query classes I: logspace oracle machines","volume":"18","author":"Stewart I. A.","year":"1993","journal-title":"Fund. Inform."},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90109-7"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01195200"},{"journal-title":"Discrete Appl. Math.","article-title":"Finding regular subgraphs in both arbitrary and planar graphs","author":"Stewart A. I.","key":"e_1_2_1_27_2"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55808-X_10"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19970430102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19970430102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T19:54:04Z","timestamp":1737057244000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19970430102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["10.1002\/malq.19970430102"],"URL":"https:\/\/doi.org\/10.1002\/malq.19970430102","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}