Assistant Professor for Theoretical Computer Science at the School of Computing at KAIST in Daejeon, South Korea. Main field of interest is (algorithmic) structural graph theory. 위다레흐트 세버스티언는(Sebastian Wiederrecht)는 KAIST에서 전산이론을 연구하는 조교수로, 구조적 및 알고리즘적 그래프 이론을 연구하고 있다. KAIST 부임 전 한국기초과학연구원(IBS) 산하 이산수학그룹(DIMAG)과 프랑스 LIRMM의 알고리즘, 그래프 및 조합론 그룹(AlGCo)에서 박사후연구원으로 근무했다. 2021년 베를린 공과대학교(Technische Universität Berlin, TUB)에서 컴퓨터 과학 박사 학위를 취득하였으며, 이때 이분 그래프에서 매칭 마이너 이론과 Permanent 문제에 대한 응용을 개발했다. 그의 관심 연구분야는 구조적 그래프 이론에 초점을 두고 있으며, 특히 그래프 마이너 이론과 관련된 그래프 포함 관계 이론의 발전에 주력하고 있다. 여기에는 구조 정리, 그래프 알고리즘, 매개변수화된 복잡도, 계산 문제, 라우팅 문제, 선형 대수 및 논리학과의 연관성 등이 포함된다.

위다레흐트 세버스티언는(Sebastian Wiederrecht)는 KAIST에서 전산이론을 연구하는 조교수로, 구조적 및 알고리즘적 그래프 이론을 연구하고 있다. KAIST 부임 전 한국기초과학연구원(IBS) 산하 이산수학그룹(DIMAG)과 프랑스 LIRMM의 알고리즘, 그래프 및 조합론 그룹(AlGCo)에서 박사후연구원으로 근무했다. 2021년 베를린 공과대학교(Technische Universität Berlin, TUB)에서 컴퓨터 과학 박사 학위를 취득하였으며, 이때 이분 그래프에서 매칭 마이너 이론과 Permanent 문제에 대한 응용을 개발했다. 그의 관심 연구분야는 구조적 그래프 이론에 초점을 두고 있으며, 특히 그래프 마이너 이론과 관련된 그래프 포함 관계 이론의 발전에 주력하고 있다. 여기에는 구조 정리, 그래프 알고리즘, 매개변수화된 복잡도, 계산 문제, 라우팅 문제, 선형 대수 및 논리학과의 연관성 등이 포함된다.

A note on the 2-Factor Hamiltonicity Conjecture

Braces of Perfect Matching Width 2

Killing a vortex

Excluding a Planar Matching Minor in Bipartite Graphs

Colouring Non-Even Digraphs

Matching Theory and Barnette's Conjecture

Even Circuits in Oriented Matroids

Digraphs of Directed Treewidth One

On chordal graph and line graph squares

Excluding an induced wheel minor in graphs without large induced stars

Twin-width one

Obstructions to Erdös-Pósa Dualities for Minors

Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces

A Flat Wall Theorem for Matching Minors in Bipartite Graphs

Packing even directed circuits quarter integrally

Approximating branchwidth on parametric extensions of planarity

Excluding a single-crossing matching minor

Kernelization for Graph Packing Problems via Rainbow Matching

Killing a Vortex

Directed Width Parameters on Semicomplete Digraphs

Parameterized Algorithms for Directed Modular Width

On Polynomial-Time Congestion-Free Software-Defined Network Updates

Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs

Congestion-Free Rerouting of Flows on DAGs

On Perfect Linegraph Squares

Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars

Unavoidable butterfly minors in digraphs of large cycle rank

Colorful Minors

The Local Structure Theorem for Graph Minors with Finite Index

Catching Rats in  H-minor-free Graphs

Excluding Pinched Spheres

The Erdős-Pósa property for circle graphs as vertex-minors

On graphs with a simple structure of maximal cliques

Polynomial Bounds for the Graph Minor Structure Theorem

Bounds on treewidth via excluding disjoint unions of cycles

Generating strongly 2-connected digraphs

Treewidth, Hadwiger Number, and Induced Minors

Unavoidable induced subgraphs in graphs with complete bipartite induced minors

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star

Excluding Surfaces as Minors in Graphs

Odd-Minors I: Excluding small parity breaks

Two Disjoint Alternating Paths in Bipartite Graphs

Parametrised Algorithms for Directed Modular Width

The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs

Matching Minors in Bipartite Graphs

The Strong Colors of Flowers - The Structure of Graphs with Chordal Squares

Congestion-free rerouting of flows on dags

Cyclewidth and the grid theorem for perfect matching width of bipartite graphs

Parameterized algorithms for directed modular width

Colouring non-even digraphs

Digraphs of directed treewidth one

Excluding a planar matching minor in bipartite graphs

Kernelization for graph packing problems via rainbow matching

On polynomial-time congestion-free software-defined network updates

Matching theory and Barnette's conjecture

Directed width parameters on semicomplete digraphs

Excluding surfaces as minors in graphs

Packing even directed circuits quarter-integrally

Excluding single-crossing matching minors in bipartite graphs

Dimitrios M. Thilikos

Meike Hatzel

Raphael Steiner

Saeed Amiri

Stefan Schmid

Archontia C. Giannopoulou

Maximilian Gorsky

Evangelos Protopapas

Stephan Kreutzer

J. Pascal Gollin

O-joung Kwon

Roman Rabinovich

Martin Milanič

Clément Dallard

Ken-ichi Kawarabayashi

Carolin Rehs

Dominique Komander

Giannos Stamoulis

David R. Wood

Maria Chudnovsky

Sebastian Wiederrecht

Changing a given configuration in a graph into another one is known as a re- configuration problem. Such problems have recently received much interest in the context of algorithmic graph theory. We initiate the theoretical study of the following reconfiguration problem: How to reroute unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NP-hard already for flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general , deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Both NP-hardness proofs are non-trivial. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows.

The Graph Minors Structure Theorem of Robertson and Seymour asserts that, for every graph H , every H -minor-free graph can be obtained by clique-sums of “almost embeddable” graphs. Here a graph is “almost embeddable” if it can be obtained from a graph of bounded Euler-genus by pasting graphs of bounded pathwidth in an “orderly fashion” into a bounded number of faces, called the vortices , and then adding a bounded number of additional vertices, called apices , with arbitrary neighborhoods. Our main result is a full classification of all graphs H for which the use of vortices in the theorem above can be avoided. To this end, we identify a (parametric) graph and prove that all -minor-free graphs can be obtained by clique-sums of graphs embeddable in a surface of bounded Euler-genus after deleting a bounded number of vertices. We show that this result is tight in the sense that the appearance of vortices cannot be …

A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition. It was introduced by Norine and intended as a tool for the structural study of matching covered graphs, especially in the context of Pfaffian orientations. Norine conjectured that graphs of high perfect matching width contain a large grid as a matching minor, similar to the result on treewidth by Robertson and Seymour. In this paper we obtain the first results on perfect matching width since its introduction. For the restricted case of bipartite graphs, we show that perfect matching width is equivalent to directed treewidth and thus, the Directed Grid Theorem by Kawarabayashi and Kreutzer for directed treewidth implies Norine’s conjecture.

Many well-known \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {NP}$$\end{document}-hard algorithmic problems on directed graphs resist efficient parameterizations with most known width measures for directed graphs, such as directed treewidth, DAG-width, Kelly-width and many others. While these focus on measuring how close a digraph is to an oriented tree resp. a directed acyclic graph, in this paper, we investigate directed modular width as a parameter, which is closer to the concept of clique-width. We investigate applications of modular decompositions of directed graphs to a wide range of algorithmic problems and derive FPT algorithms for several well-known digraph …

A colouring of a digraph as defined by Erdos and Neumann-Lara in 1980 is a vertex-colouring such that no monochromatic directed cycles exist. The minimal number of colours required for such a colouring of a loopless digraph is defined to be its dichromatic number. This quantity has been widely studied in the last decades and can be considered as a natural directed analogue of the chromatic number of a graph. A digraph D is called even if for every 0-1-weighting of the edges it contains a directed cycle of even total weight. We show that every non-even digraph has dichromatic number at most 2 and an optimal colouring can be found in polynomial time. We strengthen a previously known NP-hardness result by showing that deciding whether a directed graph is 2-colourable remains NP-hard even if it contains a feedback vertex set of bounded size.

Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes defined by finitely many forbidden induced subgraphs. Their result also implies a characterization of graph classes defined by finitely many forbidden induced subgraphs that are -bounded, that is, treewidth can only be large due to the presence of a large clique. This condition is known to be satisfied for any graph class with bounded tree-independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milani\v{c}, and \v{S}torgel in 2024. Dallard et al. conjectured that -boundedness is actually equivalent to bounded tree-independence number. We address this conjecture in the context of graph classes defined by finitely many forbidden induced subgraphs and prove it for the case of graph classes excluding an induced star. We also prove it for subclasses of the class of line graphs, determine the exact values of the tree-independence numbers of line graphs of complete graphs and line graphs of complete bipartite graphs, and characterize the tree-independence number of -free graphs, which implies a linear-time algorithm for its computation. Applying the algorithmic framework provided in a previous paper of the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes.

We characterise digraphs of directed treewidth one in terms of forbidden butterfly minors and in terms of the structure of the cycle hypergraph to a digraph D, ie the hypergraph on vertex set V (D) whose hyperedges correspond to the vertex sets of directed cycles in D.

The notion of matching minors is a specialisation of minors fit for the study of graphs with perfect matchings. Matching minors have been used to give a structural description of bipartite graphs on which the number of perfect matchings can be computed efficiently, based on a result of Little, by McCuaig et al. in 1999. In this paper we generalise basic ideas from the graph minor series by Robertson and Seymour to the setting of bipartite graphs with perfect matchings. We introduce a version of Erdős-Pósa property for matching minors and find a direct link between this property and planarity. From this, it follows that a class of bipartite graphs with perfect matchings has bounded perfect matching width if and only if it excludes a planar matching minor. We also present algorithms for bipartite graphs of bounded perfect matching width for a matching version of the disjoint paths problem, matching minor containment, and for …

We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021]. We apply the rainbow matching technique on two (di) graph packing problems, namely the TRIANGLE-PACKING IN TOURNAMENT problem (TPT), where we ask for a packing of k directed triangles in a tournament, and the INDUCED 2-PATH-PACKING (I2PP) where we ask for a packing of k induced paths of length two in a graph. The existence of a sub-quadratic kernels for these problems was proven for the first time in [Fomin, Le, Lokshtanov, Saurabh, Thomassé, Zehavi. ACM Trans. Algorithms, 2019], where they gave a kernel of 𝒪 (k 3/2) vertices and 𝒪 (k 5/3) vertices respectively. In the same paper it was questioned whether these bounds can be (optimally …

The branchwidth of a graph has been introduced by Roberson and Seymour as a measure of the tree-decomposability of a graph, alternative to treewidth. Branchwidth is polynomially computable on planar graphs by the celebrated “Ratcatcher”-algorithm of Seymour and Thomas. We investigate an extension of this algorithm to minor-closed graph classes, further than planar graphs, as follows: Let be a graph embeddable in the torus and be a graph embeddable in the projective plane. We prove that every -minor free graph G contains a subgraph where the difference between the branchwidth of G and the branchwidth of is bounded by some constant, depending only on and . Moreover, the graph admits a tree decomposition where all torsos are planar. This decomposition can be used for deriving a constant-additive approximation for branchwidth: For -minor free graphs, there is a constant c …

We consider the SDN network update problem in which a controller wants to update the routes of k (unsplittable) flows from their old paths to the new paths, consistently, i.e., without temporary congestion. As updates communicated by the controller take effect asynchronously, the challenge is to perform these updates fast, i.e., using a minimal number of rounds (controller interactions). We present the first fast, i.e., polynomial-time solution for scheduling such congestion-free network updates, for two flows and in the node ordering model. We also show that the problem is already NP-hard for six flows. We complement our formal results with simulations.

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian. A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity. As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14 …

The map of relations between the different directed width measures in general still has some blank spots. In this work we fill in many of these open relations for the restricted class of semicomplete digraphs. To do this we show the parametrical equivalence between directed path-width, directed tree-width, DAG-width, and Kelly-width. Moreover, we show that directed (linear) clique-width is upper bounded in a function of directed tree-width on semicomplete digraphs. In general the algorithmic use of many of these parameters is fairly restricted. On semicomplete digraphs our results allow to combine the nice computability of directed tree-width with the algorithmic power of directed clique-width. Moreover, our results have the effect that on semicomplete digraphs every digraph problem, which is describable in monadic second-order logic on quantification over vertices and vertex sets, is fixed parameter tractable for all …

Let and be minor-closed graph classes. We say that the pair is an Erdös-Pósa pair (EP-pair) if there exists a function such that for every and every graph , either has pairwise vertex-disjoint sub graphs which do not belong to , or there exists a set of size at most for which . The classic result of Erdös and Pósa says that if is the class of forests, then is an EP-pair for all graph classes . A minor-closed graph class is an EP-counterexample for if is minimal with the property that is not an EP-pair. In this paper, we prove that for every minor-closed graph class the set of all EP-counterexamples for is finite. In particular, we provide a complete characterization of for every and give a constructive upper bound on its size. We show that each class in can be described as the set of all minors of some, suitably defined, sequence of grid-like graphs . Moreover, each admits a half-integral packing, i.e., copies of …

We introduce an annotated extension of treewidth that measures the contribution of a vertex set to the treewidth of a graph This notion provides a graph distance measure to some graph property : A vertex set is a -treewidth modulator of to if the treewidth of in is at most and its removal gives a graph in This notion allows for a version of the Graph Minors Structure Theorem (GMST) that has no need for apices and vortices: -minor free graphs are those that admit tree-decompositions whose torsos have -treewidth modulators to some surface of Euler-genus This reveals that minor-exclusion is essentially tree-decomposability to a ``modulator-target scheme'' where the modulator is measured by its treewidth and the target is surface embeddability. We then fix the target condition by demanding that is some particular surface and define a ``surface extension'' of treewidth, where is the minimum for which admits a tree-decomposition whose torsos have a -treewidth modulator to being embeddable in We identify a finite collection of parametric graphs and prove that the minor-exclusion of the graphs in precisely determines the asymptotic behavior of for every surface It follows that the collection bijectively corresponds to the ``surface obstructions'' for i.e., surfaces that are minimally non-contained in

In this work we investigate the chordality of squares and line graph squares of graphs. We prove a sufficient condition for the chordality of squares of graphs not containing induced cycles of length at least five. Moreover, we characterize the chordality of graph squares by forbidden subgraphs. Transferring that result to line graphs allows us to characterize the chordality of line graph squares.

The Graph Minor Structure Theorem, originally proven by Robertson and Seymour [JCTB, 2003], asserts that there exist functions such that for every non-planar graph with , every -minor-free graph can be obtained via the clique-sum operation from graphs which embed into surfaces where does not embed after deleting at most many vertices with up to at most many ``vortices'' which are of ``depth'' at most . In the proof presented by Robertson and Seymour the functions and are non-constructive. Kawarabayashi, Thomas, and Wollan [arXiv, 2020] found a new proof showing that . While believing that this bound was the best their methods could achieve, Kawarabayashi, Thomas, and Wollan conjectured that and can be improved to be polynomials. In this paper we confirm their conjecture and prove that . Our proofs are fully constructive and yield a polynomial-time algorithm that either finds as a minor in a graph or produces a clique-sum decomposition for as above.

Treewidth and Hadwiger number are two of the most important parameters in structural graph theory. This paper studies graph classes in which large treewidth implies the existence of a large complete graph minor. To formalise this, we say that a graph class is (tw,had)-bounded if there is a function (called the (tw,had)-bounding function) such that tw (had ) for every graph . We characterise (tw,had)-bounded graph classes as those that exclude some planar graph as an induced minor, and use this characterisation to show that every proper vertex-minor-closed class is (tw,had)-bounded. Furthermore, we demonstrate that any (tw,had)-bounded graph class has a (tw,had)-bounding function in O(had polylog(had )). Our bound comes from the bound for the Grid Minor Theorem given by Chuzhoy and Tan, and any quantitative improvement to their result will lead directly to an improvement to our result. More strongly, we conjecture that every (tw,had)-bounded graph class has a linear (tw,had)-bounding function. In support of this conjecture, we show that it holds for the class of outer-string graphs, and for a natural generalisation of outer-string graphs: intersection graphs of strings rooted at the boundary of a fixed surface. We also verify our conjecture for low-rank perturbations of circle graphs, which is an important step towards verifying it for all proper vertex-minor-closed classes.

We prove the existence of a computable function f ∶ℕ→ℕ such that for every integer k and every digraph D , either D contains a collection C of k directed cycles of even length such that no vertex of D belongs to more than four cycles in C , or there exists a set S ⊆ V ( D ) of size at most f ( k ) such that D − S has no directed cycle of even length. Moreover, we provide an algorithm that finds one of the two outcomes of this statement in time g ( k ) n O (1) for some computable function g ∶ ℕ→ℕ. Our result unites two deep fields of research from the algorithmic theory for digraphs: The study of the Erdős-P ó sa property of digraphs and the study of the Even Dicycle Problem . The latter is the decision problem which asks if a given digraph contains an even dicycle and can be traced back to a question of Pólya from 1913. It remained open until a polynomial time algorithm was finally found by Robertson, Seymour, and Thomas (Ann. of …

By a seminal result of Valiant, computing the permanent of (0,1)-matrices is, in general, #P-hard. In 1913 Polya asked for which (0,1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding K 3,3 as a matching minor . This was turned into a polynomial time algorithm by McCuaig, Robertson, Seymour, and Thomas in 1999. However, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K 3,3 . Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0,1)-matrices can be computed efficiently. In this paper we unify the two results above into a single, more …

Sebastian Wiederrecht's Lab

교수님 소개

위다레흐트 세버스티언

연구실 소개

연구실 키워드

알럼나이가 간 회사

연구실 지원 방법

대우 조건

연도별 논문 인용수

저널 & 학회 논문 출판 수

연구실 논문 목록

A note on the 2-Factor Hamiltonicity Conjecture

Braces of Perfect Matching Width 2

Excluding an induced wheel minor in graphs without large induced stars

연구실 보유 특허

대학별 입시끈

우리 연구실 모집

교수님 소개

위다레흐트 세버스티언

연구실 키워드

알럼나이가 간 회사

연구실 지원 방법

대우 조건

연도별 논문 인용수

저널 & 학회 논문 출판 수

연구실 논문 목록

A note on the 2-Factor Hamiltonicity Conjecture

Braces of Perfect Matching Width 2

Excluding an induced wheel minor in graphs without large induced stars

연구실 보유 특허

최근 3년간 연구실적 높은 연구실

대학별 입시끈

우리 연구실 모집