Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second ‐ Order Logic
作者:
Iain A. Stewart,
期刊:
Mathematical Logic Quarterly
(WILEY Available online 1997)
卷期:
Volume 43,
issue 1
页码: 1-21
ISSN:0942-5616
年代: 1997
DOI:10.1002/malq.19970430102
出版商: WILEY‐VCH Verlag Berlin GmbH
关键词: Descriptive complexity theory;Definability in second order logic;Complexity of computation;Monadic ∑ 11;Monadic Π 11;Ehrenfeucht ‐ Fraïssé game;Ajtai ‐ Fagin game
数据来源: WILEY
摘要:
AbstractWe 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 t
点击下载:
PDF
(1245KB)
返 回