Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity – ScienceOpen
22
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity

      Preprint
      , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighborhood diversity. A classical theorem of Courcelle states that any graph property definable in MSO is decidable in linear time on graphs of bounded treewidth. Algorithmic metatheorems like Courcelle's serve to generalize known positive results on various graph classes. We explore and extend three previously studied MSO extensions: global and local cardinality constraints (CardMSO and MSO-LCC) and optimizing a fair objective function (fairMSO). First, we show how these fragments relate to each other in expressive power and highlight their (non)linearity. On the side of neighborhood diversity, we show that combining the linear variants of local and global cardinality constraints is possible while keeping the linear runtime but removing linearity of either makes this impossible, and we provide a polynomial time algorithm for the hard case. Furthemore, we show that even the combination of the two most powerful fragments is solvable in polynomial time on graphs of bounded treewidth.

          Related collections

          Most cited references21

          • Record: found
          • Abstract: not found
          • Article: not found

          The monadic second-order logic of graphs. I. Recognizable sets of finite graphs

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Easy problems for tree-decomposable graphs

                Bookmark

                Author and article information

                Journal
                2017-03-01
                Article
                1703.00544
                427943d5-dca8-4fff-8692-61a78434d90d

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                03D15
                cs.CC cs.LO

                Theoretical computer science
                Theoretical computer science

                Comments

                Comment on this article