Lars Jaffke
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Lars Jaffke has a total of 56 co-authors. Here are the top co-authors by number of shared publications:
- Hans L. Bodlaender
Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
7 shared publications - O-Joung Kwon
Department of Mathematics, Hanyang University, Seoul, South Korea
7 shared publications - Geevarghese Philip
Chennai Mathematical Institute
6 shared publications - Jan Arne Telle
Department of Informatics University of Bergen Norway
6 shared publications - Paloma T. Lima
University of Bergen Norway
5 shared publications - Paloma T. Lima
IT University of Copenhagen
5 shared publications
Latest Publications
- Open Access
- 7 April 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (2) , 1-12
A Tight Quasi-Polynomial Bound for Global Label Min-Cut
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 (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the \(st\) -cut version of the problem is known to be \(\textsf{NP}\) -hard, the above global cut version is known to admit a quasi-polynomial randomized \(n^{\mathcal{O}(\log\mathrm{OPT})}\) -time algorithm. They consider this as “strong evidence that this problem is in \(\textsf{P}\) .” We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time \((np)^{o(\log n/(\log\log n)^{2})}\) would contradict the Exponential Time Hypothesis, where \( n \) is the number of vertices, and \( p \) is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is \(\textsf{W}\) [1]-hard when parameterized by the number of uncut labels . In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph.- 7 April 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (2) , 1-12
Open AccessA Tight Quasi-Polynomial Bound for Global Label Min-Cut
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 (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the \(st\) -cut version of the problem is known to be \(\textsf{NP}\) -hard, the above global cut version is known to admit a quasi-polynomial randomized \(n^{\mathcal{O}(\log\mathrm{OPT})}\) -time algorithm. They consider this as “strong evidence that this problem is in \(\textsf{P}\) .” We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time \((np)^{o(\log n/(\log\log n)^{2})}\) would contradict the Exponential Time Hypothesis, where \( n \) is the number of vertices, and \( p \) is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is \(\textsf{W}\) [1]-hard when parameterized by the number of uncut labels . In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph. - Open Access
- 13 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1073
Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
- 13 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1073
Open AccessHamiltonicity parameterized by mim-width is (indeed) para-NP-hard
- 2 January 2026
- Published by Springer Nature
- p. 286-301
A Parameterized Complexity Analysis of Bounded Height Depth-First Search Trees
- 2 January 2026
- Published by Springer Nature
- p. 286-301
A Parameterized Complexity Analysis of Bounded Height Depth-First Search Trees
- Open Access
- 4 July 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (3) , P3.36
Treewidth is NP-Complete on Cubic Graphs
In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid, and on cubic line graphs.
- 4 July 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (3) , P3.36
Open AccessTreewidth is NP-Complete on Cubic Graphs
In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid, and on cubic line graphs.
- 16 December 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (4) , 3140-3149
Taming Graphs with No Large Creatures and Skinny Ladders
We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class [Formula: see text] there exists a constant [Formula: see text] such that no member of [Formula: see text] contains a [Formula: see text]-creature as an induced subgraph or a [Formula: see text]-skinny-ladder as an induced minor, then there exists a polynomial [Formula: see text] such that every [Formula: see text] contains at most [Formula: see text] minimal separators. By a result of Fomin, Todinca, and Villanger [ SIAM J. Comput., 44 (2015), pp. 54–87] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from [Formula: see text]. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).
- 16 December 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (4) , 3140-3149
Taming Graphs with No Large Creatures and Skinny Ladders
We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class [Formula: see text] there exists a constant [Formula: see text] such that no member of [Formula: see text] contains a [Formula: see text]-creature as an induced subgraph or a [Formula: see text]-skinny-ladder as an induced minor, then there exists a polynomial [Formula: see text] such that every [Formula: see text] contains at most [Formula: see text] minimal separators. By a result of Fomin, Todinca, and Villanger [ SIAM J. Comput., 44 (2015), pp. 54–87] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from [Formula: see text]. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).
- Open Access
- 4 November 2024
- Published by Springer Nature in Algorithmica
- Vol. 87 (4) , 465-506
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna (ACM Trans Comput Theory 9:1–36, 2018), that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, ( q -)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, Capacitated Vertex Cover and Bipartite Bandwidth.
- 4 November 2024
- Published by Springer Nature in Algorithmica
- Vol. 87 (4) , 465-506
Open AccessXNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna (ACM Trans Comput Theory 9:1–36, 2018), that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, ( q -)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, Capacitated Vertex Cover and Bipartite Bandwidth.
- Open Access
- 18 December 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (1) , 110-148
Classes of intersection digraphs with good algorithmic properties
While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions towards a better understanding of the algorithmic treatment of intersection digraphs. First, we introduce natural classes of intersection digraphs that generalize several classes studied in the literature. Second, we define the directed locally checkable vertex (DLCV) problems, which capture many well‐studied problems on digraphs, such as (Independent) Dominating Set, Kernel, and ‐Homomorphism. Third, we give a new width measure of digraphs, bi‐mim‐width, and show that the DLCV problems are polynomial‐time solvable when we are provided a decomposition of small bi‐mim‐width. Fourth, we show that several classes of intersection digraphs have bounded bi‐mim‐width, implying that we can solve all DLCV problems on these classes in polynomial time given an intersection representation of the input digraph. We identify reflexivity as a useful condition to obtain intersection digraph classes of bounded bi‐mim‐width, and therefore to obtain positive algorithmic results.
- 18 December 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (1) , 110-148
Open AccessClasses of intersection digraphs with good algorithmic properties
While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions towards a better understanding of the algorithmic treatment of intersection digraphs. First, we introduce natural classes of intersection digraphs that generalize several classes studied in the literature. Second, we define the directed locally checkable vertex (DLCV) problems, which capture many well‐studied problems on digraphs, such as (Independent) Dominating Set, Kernel, and ‐Homomorphism. Third, we give a new width measure of digraphs, bi‐mim‐width, and show that the DLCV problems are polynomial‐time solvable when we are provided a decomposition of small bi‐mim‐width. Fourth, we show that several classes of intersection digraphs have bounded bi‐mim‐width, implying that we can solve all DLCV problems on these classes in polynomial time given an intersection representation of the input digraph. We identify reflexivity as a useful condition to obtain intersection digraph classes of bounded bi‐mim‐width, and therefore to obtain positive algorithmic results.
- Open Access
- 23 September 2023
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (4) , 1049-1081
b-Coloring Parameterized by Clique-Width
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva (Algorithmica 80(1), 104–115, 2018) and Bonomo et al. (Graphs and Combinatorics 25(2), 153–167, 2009). This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is $$\textsf{FPT}$$ when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for $$b$$ -Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.- 23 September 2023
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (4) , 1049-1081
Open Accessb-Coloring Parameterized by Clique-Width
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva (Algorithmica 80(1), 104–115, 2018) and Bonomo et al. (Graphs and Combinatorics 25(2), 153–167, 2009). This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is $$\textsf{FPT}$$ when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for $$b$$ -Coloring and Fall Coloring are tight under the Exponential Time Hypothesis. - Open Access
- 31 March 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 346 (8)
On the maximum number of edges in planar graphs of bounded degree and matching number
- 31 March 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 346 (8)
Open AccessOn the maximum number of edges in planar graphs of bounded degree and matching number
- Open Access
Treewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9, by showing that Treewidth is NP-complete on cubic graphs.
Open AccessTreewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9, by showing that Treewidth is NP-complete on cubic graphs.