Lars Jaffke
YOU?
Author Swipe
View article: Treewidth is NP-Complete on Cubic Graphs
Treewidth is NP-Complete on Cubic Graphs Open
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 …
View article: Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard Open
We prove that Hamiltonian Path and Hamiltonian Cycle are NP-hard on graphs of linear mim-width 26, even when a linear order of the input graph with mim-width 26 is provided together with input. This fills a gap left by a broken proof of th…
View article: A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees Open
Computing bounded depth decompositions is a bottleneck in many applications of the treedepth parameter. The fastest known algorithm, which is due to Reidl, Rossmanith, Sánchez Villaamil, and Sikdar [ICALP 2014], runs in $2^{\mathcal{O}(k^2…
View article: On Algorithmic Applications of ℱ-Branchwidth
On Algorithmic Applications of ℱ-Branchwidth Open
F-branchwidth is a framework for width measures of graphs, recently introduced by Eiben et al. [ITCS 2022], that captures tree-width, co-tree-width, clique-width, and mim-width, and several of their generalizations and interpolations. In t…
View article: XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure Open
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 fo…
View article: Diverse Pairs of Matchings
Diverse Pairs of Matchings Open
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k , ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k . Diverse Pair of Matchi…
View article: Classes of intersection digraphs with good algorithmic properties
Classes of intersection digraphs with good algorithmic properties Open
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 und…
View article: b-Coloring Parameterized by Clique-Width
b-Coloring Parameterized by Clique-Width Open
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 …
View article: Dynamic programming on bipartite tree decompositions
Dynamic programming on bipartite tree decompositions Open
We revisit a graph width parameter that we dub bipartite treewidth (btw). Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number, and is closely related to odd-minors. Intuitively, a bi…
View article: On the maximum number of edges in planar graphs of bounded degree and matching number
On the maximum number of edges in planar graphs of bounded degree and matching number Open
We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.
View article: Treewidth is NP-Complete on Cubic Graphs (and related results)
Treewidth is NP-Complete on Cubic Graphs (and related results) Open
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-compl…
View article: A tight quasi-polynomial bound for Global Label Min-Cut
A tight quasi-polynomial bound for Global Label Min-Cut Open
e 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 al…
View article: Treewidth Is NP-Complete on Cubic Graphs
Treewidth Is NP-Complete on Cubic Graphs Open
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 …
View article: Fine-grained parameterized complexity analysis of graph coloring problems
Fine-grained parameterized complexity analysis of graph coloring problems Open
The q-COLORING problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a fine-grained analysis of the complexity of q-COLORING with respect to a hierarchy of structural parameters. We sh…
View article: $b$-Coloring Parameterized by Pathwidth is XNLP-complete
$b$-Coloring Parameterized by Pathwidth is XNLP-complete Open
We show that the $b$-Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameteriz…
View article: Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation Open
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, $(s_2,t_2)$, and $(s…
View article: A tight quasi-polynomial bound for Global Label Min-Cut
A tight quasi-polynomial bound for Global Label Min-Cut Open
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 a…
View article: On the maximum number of edges in planar graphs of bounded degree and matching number
On the maximum number of edges in planar graphs of bounded degree and matching number Open
We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.
View article: Taming graphs with no large creatures and skinny ladders
Taming graphs with no large creatures and skinny ladders Open
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-s…
View article: A logic-based algorithmic meta-theorem for mim-width
A logic-based algorithmic meta-theorem for mim-width Open
We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints ($\mathsf{A\&C~DN}$ for short) which extends existential $\mathsf{MSO_1}$ with predicates for querying neighborhoods of vertex sets and fo…
View article: Classes of Intersection Digraphs with Good Algorithmic Properties
Classes of Intersection Digraphs with Good Algorithmic Properties Open
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 und…
View article: XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure Open
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 al…
View article: Taming Graphs with No Large Creatures and Skinny Ladders
Taming Graphs with No Large Creatures and Skinny Ladders Open
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced min…
View article: A Unifying Framework for Characterizing and Computing Width Measures
A Unifying Framework for Characterizing and Computing Width Measures Open
Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient a…
View article: b-Coloring Parameterized by Clique-Width
b-Coloring Parameterized by Clique-Width Open
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 […