Mählmann, Nikolas
Loading...
Preferred name
Mählmann, Nikolas
Official Name
Mählmann, Nikolas
ORCID
GND
5 results
Now showing 1 - 5 of 5
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Flipper Games for Monadically Stable Graph Classes(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023); 14 34 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Recursive Backdoors for SAT(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021); ; A strong backdoor in a formula φ of propositional logic to a tractable class C of formulas is a set B of variables of φ such that every assignment of the variables in B results in a formula from C. Strong backdoors of small size or with a good structure, e.g. with small backdoor treewidth, lead to efficient solutions for the propositional satisfiability problem SAT. In this paper we propose the new notion of recursive backdoors, which is inspired by the observation that in order to solve SAT we can independently recurse into the components that are created by partial assignments of variables. The quality of a recursive backdoor is measured by its recursive backdoor depth. Similar to the concept of backdoor treewidth, recursive backdoors of bounded depth include backdoors of unbounded size that have a certain treelike structure. However, the two concepts are incomparable and our results yield new tractability results for SAT.conference paper19 28 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Monadically stable and monadically dependent graph classes: characterizations and algorithmic meta-theoremsA graph class is monadically stable if it does not encode the class of all linear orders using first-order logic and vertex colors. This includes many sparse classes like planar graphs, bounded degree, bounded tree-width, and nowhere dense classes, but also dense classes like map graphs. More generally, a class is monadically dependent (also known as monadically NIP) if it does not encode the class of all graphs. This includes the aforementioned monadically stable classes, and also classes of bounded clique- or twin-width. Originating in model theory, monadic stability and dependence have predominantly been studied on infinite structures. In this thesis we combine tools from combinatorics and logic, to develop a theory for monadically stable and monadically dependent classes of finite graphs that is well suited for their algorithmic treatment. We obtain the following structure/non-structure dichotomy. On the structure side, we characterize monadic stability and monadic dependence by two Ramsey-theoretic properties called flip-flatness and flip-breakability. This gives rise to a larger framework: natural restrictions of flip-flatness and flip-breakability characterize nowhere denseness, bounded clique- and tree-width, and shrub- and tree-depth. On the non-structure side, we characterize monadic stability and monadic dependence by explicitly listing few families of forbidden induced subgraphs. We show the algorithmic applicability of our characterizations by proving new tractability and hardness results for the first-order model checking problem. Given a graph G and a first-order formula phi, we want to check whether G satisfies phi. It is conjectured that a hereditary graph class admits fixed-parameter tractable model checking if and only if it is monadically dependent. Building on flip-flatness, we prove a game characterization of monadic stability called Flipper game. Using the game tree of the Flipper game as a decomposition of the input graph, we show that first-order model checking is fixed-parameter tractable on every monadically stable graph class. This confirms an important case of the tractability side of the model checking conjecture. Using the forbidden induced subgraph characterization for monadically dependent classes, we completely resolve the hardness side: we show that first-order model checking is AW[*]-hard on every hereditary graph class that is not monadically dependent.doctoral thesis888 641 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023); ; ; Monadically stable and monadically NIP classes of structures were initially studied in the context of model theory and defined in logical terms. They have recently attracted attention in the area of structural graph theory, as they generalize notions such as nowhere denseness, bounded cliquewidth, and bounded twinwidth. Our main result is the - to the best of our knowledge first - purely combinatorial characterization of monadically stable classes of graphs, in terms of a property dubbed flip-flatness. A class C of graphs is flip-flat if for every fixed radius r, every sufficiently large set of vertices of a graph G ∈ C contains a large subset of vertices with mutual distance larger than r, where the distance is measured in some graph G' that can be obtained from G by performing a bounded number of flips that swap edges and non-edges within a subset of vertices. Flip-flatness generalizes the notion of uniform quasi-wideness, which characterizes nowhere dense classes and had a key impact on the combinatorial and algorithmic treatment of nowhere dense classes. To obtain this result, we develop tools that also apply to the more general monadically NIP classes, based on the notion of indiscernible sequences from model theory. We show that in monadically stable and monadically NIP classes indiscernible sequences impose a strong combinatorial structure on their definable neighborhoods. All our proofs are constructive and yield efficient algorithms.conference paper20 36 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Combinatorial and Algorithmic Aspects of Monadic Stability(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022); ; ; ; Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Monadically stable classes, originating from model theory, generalize nowhere dense classes and close them under transductions, i.e. transformations defined by colorings and simple first-order interpretations. In this work we aim to extend some combinatorial and algorithmic properties of nowhere dense classes to monadically stable classes of finite graphs. We prove the following results. - For every monadically stable class C and fixed integer s ≥ 3, the Ramsey numbers R_C(s,t) are bounded from above by 𝒪(t^{s-1-δ}) for some δ > 0, improving the bound R(s,t) ∈ 𝒪(t^{s-1}/(log t)^{s-1}) known for the class of all graphs and the bounds known for k-stable graphs when s ≤ k. - For every monadically stable class C and every integer r, there exists δ > 0 such that every graph G ∈ C that contains an r-subdivision of the biclique K_{t,t} as a subgraph also contains K_{t^δ,t^δ} as a subgraph. This generalizes earlier results for nowhere dense graph classes. - We obtain a stronger regularity lemma for monadically stable classes of graphs. - Finally, we show that we can compute polynomial kernels for the independent set and dominating set problems in powers of nowhere dense classes. Formerly, only fixed-parameter tractable algorithms were known for these problems on powers of nowhere dense classes.conference paper20 44