Mateus de Oliveira Oliveira: Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs

Lunch is served at 12:00 noon (register at doodle.com/66sqtfib9k9ir79x by Thursday Mar 14 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

We introduce the notion of z-topological orderings for digraphs. We prove that given a digraph G admitting a z-topological ordering, we may count the number of subgraphs of G that satisfy a monadic second order formula φ and that are the union of k directed paths in time f(φ, k, z)•n^O(k•z) . Our result implies the polynomial time solvability of a vast number of natural counting problems on digraphs admitting z- topological orderings for constant z. For instance, we are able to answer in polynomial time questions of the form "How many planar subgraphs of G are the union of k directed paths?" Concerning the relationship between z-topological orderability and other digraph measures, we observe that any digraph of directed path-width d has a z-topological ordering for z ≤ 2d + 1. Since graphs of directed path-width can have both arbitrarily large undirected tree width and arbitrarily large clique width, our result provides for the first time a suitable way of partially transposing metatheorems developed in the context of the monadic second order logic of graphs of bounded undirected tree width and bounded clique width to the realm of digraph width measures that are closed under taking subgraphs and whose constant levels incorporate families of graphs of arbitrarily large tree width and arbitrarily large clique width.