Lower bounds on the complexity of MSO1 model-checking

作者：

Highlights：

• Efficient coloured MSO1 properties on monotone graph classes need small tree-width.

• This extends recent Kreutzer–Tazari to a different class of properties.

• There is likely no monotone and algorithmically useful digraph width measures.

摘要

•Efficient coloured MSO1 properties on monotone graph classes need small tree-width.•This extends recent Kreutzer–Tazari to a different class of properties.•There is likely no monotone and algorithmically useful digraph width measures.

论文关键词：Graph MSO logic,Tree-width,Digraph width,Intractability

论文评审过程：Received 22 June 2012, Revised 26 April 2013, Accepted 15 July 2013, Available online 22 July 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.07.005