4 citations · 13 across the 17 of their papers we have counts for
10 papers · 1 filter
Treedepth vs circumference
Marcin Briański, Gwenaël Joret, Konrad Majewski +3
The circumference of a graph is the length of a longest cycle in , or if has no cycle. Birmelé (2003) showed that the treewidth of a graph is at most its c…
-Coloring Parameterized by Pathwidth is XNLP-complete
Lars Jaffke, Paloma T. Lima, Roohani Sharma
We show that the -Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexit…
On weighted graph separation problems and flow-augmentation
Eun Jung Kim, Tomáš Masařík, Marcin Pilipczuk +2
One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of \te…
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
Esther Galby, Sandor Kisfaludi-Bak, Daniel Marx +1
In the Directed Steiner Network problem, the input is a directed graph G, a subset T of k vertices of G called the terminals, and a demand graph D on T. The task is to find a subgr…
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
Esther Galby, Daniel Marx, Philipp Schepper +2
The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameter…
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
Meike Hatzel, Lars Jaffke, Paloma T. Lima +4
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph , pairs of ve…