29 citations · 63 across the 22 of their papers we have counts for
6 papers · 1 filter
-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…
A tight quasi-polynomial bound for Global Label Min-Cut
Lars Jaffke, Paloma T. Lima, Tomáš Masařík +2
We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi)graph are labeled (o…
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…
On the maximum number of edges in planar graphs of bounded degree and matching number
Lars Jaffke, Paloma T. Lima
We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.
Taming graphs with no large creatures and skinny ladders
Jakub Gajarský, Lars Jaffke, Paloma T. Lima +4
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class there exists a constant such that no member of $\mathcal{G}…
A logic-based algorithmic meta-theorem for mim-width
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints ( for short) which extends existential with…