BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Sebastian Siebertz

Sebastian Siebertz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete Mathematicsmath.COData Structures and AlgorithmsLogic in Computer Sciencemath.LODistributed, Parallel, and Cluster ComputingComputational Complexity

Catalog footprint

What is connected

15works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2022arXiv

A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems

A graph vertex-subset problem defines which subsets of the vertices of an input graph are feasible solutions. We view a feasible solution as a set of tokens placed on the vertices of the graph. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size $k$, whether it is possible to transform one into the other by a sequence of token slides (along edges of the graph) or token jumps (between arbitrary vertices of the graph) such that each intermediate set remains a feasible solution of size $k$. Many algorithmic questions present themselves in the form of reconfiguration problems: Given the description of an initial system state and the description of a target state, is it possible to transform the system from its initial state into the target one while preserving certain properties of the system in the process? Such questions have received a substantial amount of attention under the so-called combinatorial reconfiguration framework. We consider reconfiguration variants of three fundamental underlying graph vertex-subset problems, namely Independent Set, Dominating Set, and Connected Dominating Set. We survey both older and more recent work on the parameterized complexity of all three problems when parameterized by the number of tokens $k$. The emphasis will be on positive results and the most common techniques for the design of fixed-parameter tractable algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Combinatorial and Algorithmic Aspects of Monadic Stability

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. - In monadically stable classes the Ramsey numbers $R(s,t)$ are bounded from above by $\mathcal{O}(t^{s-1-δ})$ for some $δ>0$, improving the bound $R(s,t)\in \mathcal{O}(t^{s-1}/(\log t)^{s-1})$ known for general graphs and the bounds known for $k$-stable graphs when $s\leq k$. - For every monadically stable class $\mathcal{C}$ and every integer $r$, there exists $δ> 0$ such that every graph $G \in \mathcal{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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Distributed domination on sparse graph classes

We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with bounded expansion. This generalizes a result of Czygrinow et al. for graphs with excluded topological minors to very general classes of uniformly sparse graphs. We demonstrate how our general algorithm can be modified and fine-tuned to compute an ($11+ε$)-approximation (for any $ε>0)$ of a minimum dominating set on planar graphs. This improves on the previously best known approximation factor of 52 on planar graphs, which was achieved by an elegant and simple algorithm of Lenzen et al.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Transducing paths in graph classes with unbounded shrubdepth

Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class $\mathscr{C}$ can be $\mathsf{FO}$-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from $\mathscr{C}$ one cannot $\mathsf{FO}$-transduce the class of all paths. This establishes one of the three remaining open questions posed by Blumensath and Courcelle about the $\mathsf{MSO}$-transduction quasi-order, even in the stronger form that concerns $\mathsf{FO}$-transductions instead of $\mathsf{MSO}$-transductions. The backbone of our proof is a graph-theoretic statement that says the following: If a graph $G$ excludes a path, the bipartite complement of a path, and a half-graph as semi-induced subgraphs, then the vertex set of $G$ can be partitioned into a bounded number of parts so that every part induces a cograph of bounded height, and every pair of parts semi-induce a bi-cograph of bounded height. This statement may be of independent interest; for instance, it implies that the graphs in question form a class that is linearly $χ$-bounded.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Parameterized Distributed Complexity Theory: A logical approach

Parameterized complexity theory offers a framework for a refined analysis of hard algorithmic problems. Instead of expressing the running time of an algorithm as a function of the input size only, running times are expressed with respect to one or more parameters of the input instances. In this work we follow the approach of parameterized complexity to provide a framework of parameterized distributed complexity. The central notion of efficiency in parameterized complexity is fixed-parameter tractability and we define the distributed analogue Distributed-FPT (for Distributed in $\{Local, Congest, Congested-Clique\}$) as the class of problems that can be solved in $f(k)$ communication rounds in the Distributed model of distributed computing, where $k$ is the parameter of the problem instance and $f$ is an arbitrary computable function. To classify hardness we introduce three hierarchies. The Distributed-WEFT-hierarchy is defined analogously to the W-hierarchy in parameterized complexity theory via reductions to the weighted circuit satisfiability problem, but it turns out that this definition does not lead to satisfying frameworks for the Local and Congest models. We then follow a logical approach that leads to a more robust theory. We define the levels of the Distributed-W-hierarchy and the Distributed-A-hierarchy that have first-order model-checking problems as their complete problems via suitable reductions.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Recursive Backdoors for SAT

A strong backdoor in a formula $ϕ$ of propositional logic to a tractable class $\mathcal{C}$ of formulas is a set $B$ of variables of $ϕ$ such that every assignment of the variables in $B$ results in a formula from $\mathcal{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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rankwidth meets stability

We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs $C$ is monadically stable if it is impossible to define arbitrarily long linear orders in vertex-colored graphs from $C$ using a fixed first-order formula. Similarly, monadic dependence corresponds to the impossibility of defining all graphs in this way. Examples of monadically stable graph classes are nowhere dense classes, which provide a robust theory of sparsity. Examples of monadically dependent classes are classes of bounded rankwidth (or equivalently, bounded cliquewidth), which can be seen as a dense analog of classes of bounded treewidth. Thus, monadic stability and monadic dependence extend classical structural notions for graphs by viewing them in a wider, model-theoretical context. We explore this emerging theory by proving the following: - A class of graphs $C$ is a first-order transduction of a class with bounded treewidth if and only if $C$ has bounded rankwidth and a stable edge relation (i.e. graphs from $C$ exclude some half-graph as a semi-induced subgraph). - If a class of graphs $C$ is monadically dependent and not monadically stable, then $C$ has in fact an unstable edge relation. As a consequence, we show that classes with bounded rankwidth excluding some half-graph as a semi-induced subgraph are linearly $χ$-bounded. Our proofs are effective and lead to polynomial time algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Regular partitions of gentle graphs

Szemeredi's Regularity Lemma is a very useful tool of extremal combinatorics. Recently, several refinements of this seminal result were obtained for special, more structured classes of graphs. We survey these results in their rich combinatorial context. In particular, we stress the link to the theory of (structural) sparsity, which leads to alternative proofs, refinements and solutions of open problems. It is interesting to note that many of these classes present challenging problems. Nevertheless, from the point of view of regularity lemma type statements, they appear as "gentle" classes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A local constant factor approximation for the minimum dominating set problem on bounded genus graphs

The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, several breakthroughs have been made on computing local approximations on sparse graphs. This paper presents a deterministic and local constant factor approximation for minimum dominating sets on bounded genus graphs, a very large family of sparse graphs. Our main technical contribution is a new analysis of a slightly modified, first-order definable variant of an existing algorithm by Lenzen et al. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on any topological arguments. We believe that our techniques can be useful for the study of local problems on sparse graphs beyond the scope of this paper.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Neighborhood complexity and kernelization for nowhere dense classes of graphs

We prove that whenever $G$ is a graph from a nowhere dense graph class $\mathcal{C}$, and $A$ is a subset of vertices of $G$, then the number of subsets of $A$ that are realized as intersections of $A$ with $r$-neighborhoods of vertices of $G$ is at most $f(r,ε)\cdot |A|^{1+ε}$, where $r$ is any positive integer, $ε$ is any positive real, and $f$ is a function that depends only on the class $\mathcal{C}$. This yields a characterization of nowhere dense classes of graphs in terms of neighborhood complexity, which answers a question posed by Reidl et al. As an algorithmic application of the above result, we show that for every fixed $r$, the parameterized Distance-$r$ Dominating Set problem admits an almost linear kernel on any nowhere dense graph class. This proves a conjecture posed by Drange et al., and shows that the limit of parameterized tractability of Distance-$r$ Dominating Set on subgraph-closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Generalised Colouring Numbers on Classes of Bounded Expansion

The generalised colouring numbers $\mathrm{adm}_r(G)$, $\mathrm{col}_r(G)$, and $\mathrm{wcol}_r(G)$ were introduced by Kierstead and Yang as generalisations of the usual colouring number, also known as the degeneracy of a graph, and have since then found important applications in the theory of bounded expansion and nowhere dense classes of graphs, introduced by Nešetřil and Ossona de Mendez. In this paper, we study the relation of the colouring numbers with two other measures that characterise nowhere dense classes of graphs, namely with uniform quasi-wideness, studied first by Dawar et al. in the context of preservation theorems for first-order logic, and with the splitter game, introduced by Grohe et al. We show that every graph excluding a fixed topological minor admits a universal order, that is, one order witnessing that the colouring numbers are small for every value of $r$. Finally, we use our construction of such orders to give a new proof of a result of Eickmeyer and Kawarabayashi, showing that the model-checking problem for successor-invariant first-order formulas is fixed-parameter tractable on classes of graphs with excluded topological minors.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Kernelization and Sparseness: the case of Dominating Set

We prove that for every positive integer $r$ and for every graph class $\mathcal G$ of bounded expansion, the $r$-Dominating Set problem admits a linear kernel on graphs from $\mathcal G$. Moreover, when $\mathcal G$ is only assumed to be nowhere dense, then we give an almost linear kernel on $\mathcal G$ for the classic Dominating Set problem, i.e., for the case $r=1$. These results generalize a line of previous research on finding linear kernels for Dominating Set and $r$-Dominating Set. However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related Connected Dominating Set problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on $H$-topological-minor-free graphs. Also, we prove that for any somewhere dense class $\mathcal G$, there is some $r$ for which $r$-Dominating Set is W[$2$]-hard on $\mathcal G$. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of $r$-Dominating Set on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Deciding first-order properties of nowhere dense graphs

Nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs and graph classes of bounded expansion. We show that deciding properties of graphs definable in first-order logic is fixed-parameter tractable on nowhere dense graph classes. At least for graph classes closed under taking subgraphs, this result is optimal: it was known before that for all classes C of graphs closed under taking subgraphs, if deciding first-order properties of graphs in C is fixed-parameter tractable, then C must be nowhere dense (under a reasonable complexity theoretic assumption). As a by-product, we give an algorithmic construction of sparse neighbourhood covers for nowhere dense graphs. This extends and improves previous constructions of neighbourhood covers for graph classes with excluded minors. At the same time, our construction is considerably simpler than those. Our proofs are based on a new game-theoretic characterisation of nowhere dense graphs that allows for a recursive version of locality-based algorithms on these classes. On the logical side, we prove a "rank-preserving" version of Gaifman's locality theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Directed Width Measures and Monotonicity of Directed Graph Searching

We consider generalisations of tree width to directed graphs, that attracted much attention in the last fifteen years. About their relative strength with respect to "bounded width in one measure implies bounded width in the other" many problems remain unsolved. Only some results separating directed width measures are known. We give an almost complete picture of this relation. For this, we consider the cops and robber games characterising DAG-width and directed tree width (up to a constant factor). For DAG-width games, it is an open question whether the robber-monotonicity cost (the difference between the minimal numbers of cops capturing the robber in the general and in the monotone case) can be bounded by any function. Examples show that this function (if it exists) is at least $f(k) > 4k/3$ (Kreutzer, Ordyniak 2008). We approach a solution by defining weak monotonicity and showing that if $k$ cops win weakly monotonically, then $O(k^2)$ cops win monotonically. It follows that bounded Kelly-width implies bounded DAG-width, which has been open since the definition of Kelly-width by Hunter and Kreutzer in 2008. For directed tree width games we show that, unexpectedly, the cop-monotonicity cost (no cop revisits any vertex) is not bounded by any function. This separates directed tree width from D-width defined by Safari in 2005, refuting his conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Vertex Disjoint Path in Upward Planar Graphs

The $k$-vertex disjoint paths problem is one of the most studied problems in algorithmic graph theory. In 1994, Schrijver proved that the problem can be solved in polynomial time for every fixed $k$ when restricted to the class of planar digraphs and it was a long standing open question whether it is fixed-parameter tractable (with respect to parameter $k$) on this restricted class. Only recently, \cite{CMPP}.\ achieved a major breakthrough and answered the question positively. Despite the importance of this result (and the brilliance of their proof), it is of rather theoretical importance. Their proof technique is both technically extremely involved and also has at least double exponential parameter dependence. Thus, it seems unrealistic that the algorithm could actually be implemented. In this paper, therefore, we study a smaller class of planar digraphs, the class of upward planar digraphs, a well studied class of planar graphs which can be drawn in a plane such that all edges are drawn upwards. We show that on the class of upward planar digraphs the problem (i) remains NP-complete and (ii) the problem is fixed-parameter tractable. While membership in FPT follows immediately from \cite{CMPP}'s general result, our algorithm has only single exponential parameter dependency compared to the double exponential parameter dependence for general planar digraphs. Furthermore, our algorithm can easily be implemented, in contrast to the algorithm in \cite{CMPP}.

0 citations0 reviewsNo code linkedOpen access