Source author record

Oliver Schaudt

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms Computational Complexity Information Theory math.IT math.OC

Catalog footprint

Research overview

19works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Discrete Optimization Methods for Group Model Selection in Compressed Sensing

In this article we study the problem of signal recovery for group models. More precisely for a given set of groups, each containing a small subset of indices, and for given linear sketches of the true signal vector which is known to be group-sparse in the sense that its support is contained in the union of a small number of these groups, we study algorithms which successfully recover the true signal just by the knowledge of its linear sketches. We derive model projection complexity results and algorithms for more general group models than the state-of-the-art. We consider two versions of the classical Iterative Hard Thresholding algorithm (IHT). The classical version iteratively calculates the exact projection of a vector onto the group model, while the approximate version (AM-IHT) uses a head- and a tail-approximation iteratively. We apply both variants to group models and analyse the two cases where the sensing matrix is a Gaussian matrix and a model expander matrix. To solve the exact projection problem on the group model, which is known to be equivalent to the maximum weight coverage problem, we use discrete optimization methods based on dynamic programming and Benders' Decomposition. The head- and tail-approximations are derived by a classical greedy-method and LP-rounding, respectively.

preprint2020arXiv

Fault-Tolerant Edge-Disjoint Paths -- Beyond Uniform Faults

The overwhelming majority of survivable (fault-tolerant) network design models assume a uniform fault model. Such a model assumes that every subset of the network resources (edges or vertices) of a given cardinality $k$ may fail. While this approach yields problems with clean combinatorial structure and good algorithms, it often fails to capture the true nature of the scenario set coming from applications. One natural refinement of the uniform model is obtained by partitioning the set of resources into vulnerable and safe resources. The scenario set contains every subset of at most $k$ faulty resources. This work studies the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest Path problem in this fault model and the Fault-Tolerant Flow problem (FTF), the counterpart of the $\ell$ -disjoint Shortest $s$ - $t$ Path problem. We present complexity results alongside exact and approximation algorithms for both models. We emphasize the vast increase in the complexity of the problem with respect to the uniform analogue, the Edge-Disjoint Paths problem.

preprint2016arXiv

Almost partitioning a 3-edge-coloured $K_{n,n}$ into 5 monochromatic cycles

We show that for any colouring of the edges of the complete bipartite graph $K_{n,n}$ with 3 colours there are 5 disjoint monochromatic cycles which together cover all but $o(n)$ of the vertices. In the same situation, 18 disjoint monochromatic cycles together cover all vertices.

preprint2016arXiv

Approximately coloring graphs without long induced paths

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on $t$ vertices, for fixed $t$ . We propose an algorithm that, given a 3-colorable graph without an induced path on $t$ vertices, computes a coloring with $\max\{5,2\lceil{\frac{t-1}{2}}\rceil-2\}$ many colors. If the input graph is triangle-free, we only need $\max\{4,\lceil{\frac{t-1}{2}}\rceil+1\}$ many colors. The running time of our algorithm is $O((3^{t-2}+t^2)m+n)$ if the input graph has $n$ vertices and $m$ edges.

preprint2016arXiv

On bounding the difference between the maximum degree and the chromatic number by a constant

We provide a finite forbidden induced subgraph characterization for the graph class $\varUpsilon_k$ , for all $k \in \mathbb{N}_0$ , which is defined as follows. A graph is in $\varUpsilon_k$ if for any induced subgraph, $Δ\leq χ-1 + k$ holds, where $Δ$ is the maximum degree and $χ$ is the chromatic number of the subgraph. We compare these results with those given in [O. Schaudt, V. Weil, On bounding the difference between the maximum degree and the clique number, Graphs and Combinatorics 31(5), 1689-1702 (2015). DOI: 10.1007/s00373-014-1468-3], where we studied the graph class $\varOmega_k$ , for $k \in \mathbb{N}_0$ , whose graphs are such that for any induced subgraph, $Δ\leq ω-1 + k$ holds, where $ω$ denotes the clique number of a graph. In particular, we give a characterization in terms of $\varOmega_k$ and $\varUpsilon_k$ of those graphs where the neighborhood of every vertex is perfect.

preprint2015arXiv

Exhaustive generation of $k$ -critical $\mathcal H$ -free graphs

We describe an algorithm for generating all $k$ -critical $\mathcal H$ -free graphs, based on a method of Hoàng et al. Using this algorithm, we prove that there are only finitely many $4$ -critical $(P_7,C_k)$ -free graphs, for both $k=4$ and $k=5$ . We also show that there are only finitely many $4$ -critical graphs $(P_8,C_4)$ -free graphs. For each case of these cases we also give the complete lists of critical graphs and vertex-critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the $3$ -colorability problem in the respective classes. Moreover, we prove that for every $t$ , the class of 4-critical planar $P_t$ -free graphs is finite. We also determine all 27 4-critical planar $(P_7,C_6)$ -free graphs. We also prove that every $P_{10}$ -free graph of girth at least five is 3-colorable, and determine the smallest 4-chromatic $P_{12}$ -free graph of girth five. Moreover, we show that every $P_{13}$ -free graph of girth at least six and every $P_{16}$ -free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.

preprint2015arXiv

Long cycles through prescribed vertices have the Erdős-Pósa property

We prove that for every graph, any vertex subset $S$ , and given integers $k,\ell$ : there are $k$ disjoint cycles of length at least $\ell$ that each contain at least one vertex from $S$ , or a vertex set of size $O(\ell \cdot k \log k)$ that meets all such cycles. This generalises previous results of Fiorini and Hendrickx and of Pontecorvi and Wollan. In addition, we describe an algorithm for our main result that runs in $O(k \log k \cdot s^2 \cdot (f(\ell) \cdot n+m))$ time, where $s$ denotes the cardinality of $S$ .

preprint2015arXiv

Recognizing k-equistable graphs in FPT time

A graph $G = (V,E)$ is called equistable if there exist a positive integer $t$ and a weight function $w : V \to \mathbb{N}$ such that $S \subseteq V$ is a maximal stable set of $G$ if and only if $w(S) = t$ . Such a function $w$ is called an equistable function of $G$ . For a positive integer $k$ , a graph $G = (V,E)$ is said to be $k$ -equistable if it admits an equistable function which is bounded by $k$ . We prove that the problem of recognizing $k$ -equistable graphs is fixed parameter tractable when parameterized by $k$ , affirmatively answering a question of Levit et al. In fact, the problem admits an $O(k^5)$ -vertex kernel that can be computed in linear time.

preprint2014arXiv

A new characterization of $P_k$ -free graphs

The class of graphs that do not contain an induced path on $k$ vertices, $P_k$ -free graphs, plays a prominent role in algorithmic graph theory. This motivates the search for special structural properties of $P_k$ -free graphs, including alternative characterizations. Let $G$ be a connected $P_k$ -free graph, $k \ge 4$ . We show that $G$ admits a connected dominating set whose induced subgraph is either $P_{k-2}$ -free, or isomorphic to $P_{k-2}$ . Surprisingly, it turns out that every minimum connected dominating set of $G$ has this property. This yields a new characterization for $P_k$ -free graphs: a graph $G$ is $P_k$ -free if and only if each connected induced subgraph of $G$ has a connected dominating set whose induced subgraph is either $P_{k-2}$ -free, or isomorphic to $C_k$ . This improves and generalizes several previous results; the particular case of $k=7$ solves a problem posed by van 't Hof and Paulusma [A new characterization of $P_6$ -free graphs, COCOON 2008]. In the second part of the paper, we present an efficient algorithm that, given a connected graph $G$ on $n$ vertices and $m$ edges, computes a connected dominating set $X$ of $G$ with the following property: for the minimum $k$ such that $G$ is $P_k$ -free, the subgraph induced by $X$ is $P_{k-2}$ -free or isomorphic to $P_{k-2}$ . As an application our results, we prove that Hypergraph 2-Colorability, an NP-complete problem in general, can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graph is $P_7$ -free.

preprint2014arXiv

Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles

We show that any complete $k$ -partite graph $G$ on $n$ vertices, with $k \ge 3$ , whose edges are two-coloured, can be covered with two vertex-disjoint monochromatic paths of distinct colours. We prove this under the necessary assumption that the largest partition class of $G$ contains at most $n/2$ vertices. This extends known results for complete and complete bipartite graphs. Secondly, we show that in the same situation, all but $o(n)$ vertices of the graph can be covered with two vertex-disjoint monochromatic cycles of distinct colours, if colourings close to a split colouring are excluded. From this we derive that the whole graph, if large enough, may be covered with 14 vertex-disjoint monochromatic cycles.

preprint2014arXiv

Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs

The square of a graph $G$ , denoted $G^2$ , is obtained from $G$ by putting an edge between two distinct vertices whenever their distance is two. Then $G$ is called a square root of $G^2$ . Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a chordal graph or even a split graph. We present a polynomial time algorithm that decides whether a given graph has a ptolemaic square root. If such a root exists, our algorithm computes one with a minimum number of edges. In the second part of our paper, we give a characterization of the graphs that admit a 3-sun-free split square root. This characterization yields a polynomial time algorithm to decide whether a given graph has such a root, and if so, to compute one.

preprint2014arXiv

Squares of $3$ -sun-free split graphs

The square of a graph $G$ , denoted by $G^2$ , is obtained from $G$ by putting an edge between two distinct vertices whenever their distance is two. Then $G$ is called a square root of $G^2$ . Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a split graph, that is, a graph in which the vertex set can be partitioned into a stable set and a clique. We give a wide range of polynomial time solvable cases for the problem of recognizing if a given graph is the square of some special kind of split graph. To the best of our knowledge, our result properly contains all previously known such cases. Our polynomial time algorithms are build on a structural investigation of graphs that admit a split square root that is 3-sun-free, and may pave the way toward a dichotomy theorem for recognizing squares of (3-sun-free) split graphs.

preprint2014arXiv

Structural parameterizations for boxicity

The boxicity of a graph $G$ is the least integer $d$ such that $G$ has an intersection model of axis-aligned $d$ -dimensional boxes. Boxicity, the problem of deciding whether a given graph $G$ has boxicity at most $d$ , is NP-complete for every fixed $d \ge 2$ . We show that boxicity is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Adiga et al., that boxicity is fixed-parameter tractable in the vertex cover number. Moreover, we show that boxicity admits an additive $1$ -approximation when parameterized by the pathwidth of the input graph. Finally, we provide evidence in favor of a conjecture of Adiga et al. that boxicity remains NP-complete when parameterized by the treewidth.

preprint2013arXiv

A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles

The ratio of the connected domination number, $γ_c$ , and the domination number, $γ$ , is strictly bounded from above by 3. It was shown by Zverovich that for every connected $(P_5,C_5)$ -free graph, $γ_c = γ$ . In this paper, we investigate the interdependence of $γ$ and $γ_c$ in the class of $(P_k,C_k)$ -free graphs, for $k \ge 6$ . We prove that for every connected $(P_6,C_6)$ -free graph, $γ_c \le γ+ 1$ holds, and there is a family of $(P_6,C_6)$ -free graphs with arbitrarily large values of $γ$ attaining this bound. Moreover, for every connected $(P_8,C_8)$ -free graph, $γ_c / γ\le 2$ , and there is a family of $(P_7,C_7)$ -free graphs with arbitrarily large values of $γ$ attaining this bound. In the class of $(P_9,C_9)$ -free graphs, the general bound $γ_c / γ\le 3$ is asymptotically sharp.

preprint2013arXiv

Claw-free t-perfect graphs can be recognised in polynomial time

A graph is called t-perfect if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We show that it can be decided in polynomial time whether a given claw-free graph is t-perfect.

preprint2013arXiv

The graph formulation of the union-closed sets conjecture

In 1979 Frankl conjectured that in a finite non-trivial union-closed collection of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs.

preprint2013arXiv

The journey of the union-closed sets conjecture

We survey the state of the union-closed sets conjecture.

preprint2013arXiv

The Price of Connectivity for Vertex Cover

The vertex cover number of a graph is the minimum number of vertices that are needed to cover all edges. When those vertices are further required to induce a connected subgraph, the corresponding number is called the connected vertex cover number, and is always greater or equal to the vertex cover number. Connected vertex covers are found in many applications, and the relationship between those two graph invariants is therefore a natural question to investigate. For that purpose, we introduce the {\em Price of Connectivity}, defined as the ratio between the two vertex cover numbers. We prove that the price of connectivity is at most 2 for arbitrary graphs. We further consider graph classes in which the price of connectivity of every induced subgraph is bounded by some real number $t$ . We obtain forbidden induced subgraph characterizations for every real value $t \leq 3/2$ . We also investigate critical graphs for this property, namely, graphs whose price of connectivity is strictly greater than that of any proper induced subgraph. Those are the only graphs that can appear in a forbidden subgraph characterization for the hereditary property of having a price of connectivity at most $t$ . In particular, we completely characterize the critical graphs that are also chordal. Finally, we also consider the question of computing the price of connectivity of a given graph. Unsurprisingly, the decision version of this question is NP-hard. In fact, we show that it is even complete for the class $Θ_2^P = P^{NP[\log]}$ , the class of decision problems that can be solved in polynomial time, provided we can make $O(\log n)$ queries to an NP-oracle. This paves the way for a thorough investigation of the complexity of problems involving ratios of graph invariants.

preprint2013arXiv

The union-closed sets conjecture almost holds for almost all random bipartite graphs

Frankl's union-closed sets conjecture states that in every finite union-closed set of sets, there is an element that is contained in at least half of the member-sets (provided there are at least two members). The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets. We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl's conjecture.

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.

Oliver Schaudt

Research overview

Is this your work?

19 publications

Discrete Optimization Methods for Group Model Selection in Compressed Sensing

Fault-Tolerant Edge-Disjoint Paths -- Beyond Uniform Faults

Almost partitioning a 3-edge-coloured $K_{n,n}$ into 5 monochromatic cycles

Approximately coloring graphs without long induced paths

On bounding the difference between the maximum degree and the chromatic number by a constant

Exhaustive generation of $k$ -critical $\mathcal H$ -free graphs

Long cycles through prescribed vertices have the Erdős-Pósa property

Recognizing k-equistable graphs in FPT time

A new characterization of $P_k$ -free graphs

Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles

Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs

Squares of $3$ -sun-free split graphs

Structural parameterizations for boxicity

A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles

Claw-free t-perfect graphs can be recognised in polynomial time

The graph formulation of the union-closed sets conjecture

The journey of the union-closed sets conjecture

The Price of Connectivity for Vertex Cover

The union-closed sets conjecture almost holds for almost all random bipartite graphs

See the researcher in context

Building this map preview

Oliver Schaudt

Research overview

Is this your work?

19 publications

Discrete Optimization Methods for Group Model Selection in Compressed Sensing

Fault-Tolerant Edge-Disjoint Paths -- Beyond Uniform Faults

Almost partitioning a 3-edge-coloured Kn,nK_{n,n}Kn,n​ into 5 monochromatic cycles

Approximately coloring graphs without long induced paths

On bounding the difference between the maximum degree and the chromatic number by a constant

Exhaustive generation of kkk-critical H\mathcal HH-free graphs

Long cycles through prescribed vertices have the Erdős-Pósa property

Recognizing k-equistable graphs in FPT time

A new characterization of PkP_kPk​-free graphs

Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles

Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs

Squares of 333-sun-free split graphs

Structural parameterizations for boxicity

A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles

Claw-free t-perfect graphs can be recognised in polynomial time

The graph formulation of the union-closed sets conjecture

The journey of the union-closed sets conjecture

The Price of Connectivity for Vertex Cover

The union-closed sets conjecture almost holds for almost all random bipartite graphs

See the researcher in context

Building this map preview

Almost partitioning a 3-edge-coloured $K_{n,n}$ into 5 monochromatic cycles

Exhaustive generation of $k$ -critical $\mathcal H$ -free graphs

A new characterization of $P_k$ -free graphs

Squares of $3$ -sun-free split graphs