Slim Tree-Cut Width.

Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it turned out that tree-cut width falls short as an edge-cut based alternative to treewidth in algorithmic aspects. This has led to the very recent introduction of a simple edge-based parameter called edge-cut width [WG 2022], which has precisely the algorithmic applications one would expect from an analogue of treewidth for edge cuts, but does not have the desired structural properties.

The Power of Cut-Based Parameters for Computing Edge-Disjoint Paths.

This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph and a set of terminal pairs and asks whether contains a set of pairwise edge-disjoint paths connecting every terminal pair in . Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3.

Counting Linear Extensions: Parameterizations by Treewidth.

We consider the -complete problem of counting the number of linear extensions of a poset ; a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e.

Solving Problems on Graphs of High Rank-Width.

A modulator in a graph is a vertex set whose deletion places the considered graph into some specified graph class. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain fixed-parameter algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width).