Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second ‐ Order Logic
Iain A. Stewart · Mathematical logic quarterly · 1997
Abstract We investigate the definability in monadic ∑11and monadic Π11of the problems REGk, of whether there is a regular subgraph of degreekin some given graph, and XREGk, of whether, for a given rooted graph, there is a regular subgraph of degreekin which the root has degreek, and their restrictions to graphs in which every vertex has degree at mostk, namely REGkkand XREGkk, respectively, fork≥ 2 (all our graphs are undirected). Our motivation partly stems from the fact (which we prove here) that REGkkand XREGkkare logspace equivalent to CONN and REACH, respectively, fork≥ 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 ‐ order reductions, monadic ∑11games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑11and monadic Π11, and we compare the definability of these problems (in monadic ∑11and monadic Π11with their computational complexity (which varies from solvable using logspace to NP ‐ complete).