Browsing Bergen Open Research Archive by Author "Jaffke, Lars"
Now showing items 120 of 21

bColoring Parameterized by CliqueWidth
Jaffke, Lars; Lima, Paloma Thome de; Lokshtanov, Daniel (Journal article; Peer reviewed, 2021)We provide a polynomialtime algorithm for bColoring on graphs of constant cliquewidth. This unifies and extends nearly all previously known polynomialtime results on graph classes, and answers open questions posed by ... 
Classes of Intersection Digraphs with Good Algorithmic Properties
Jaffke, Lars; Kwon, Ojoung; Telle, Jan Arne (Journal article; Peer reviewed, 2022)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 ... 
A complexity dichotomy for critical values of the bchromatic number of graphs
Lima, Paloma T.; Jaffke, Lars (Journal article; Peer reviewed, 2020)A bcoloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The bColoring problem asks whether a graph G has ... 
A complexity dichotomy for critical values of the bchromatic number of graphs
Jaffke, Lars; Lima, Paloma T. (Peer reviewed; Journal article, 20190820)A bcoloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The bColoring problem asks whether a graph G has ... 
Compressing permutation groups into grammars and polytopes. A graph embedding approach
Jaffke, Lars; De Oliveira Oliveira, Mateus; Tiwary, Hans Raj (Journal article; Peer reviewed, 2020)It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+G) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can ... 
Diverse Pairs of Matchings
Fomin, Fedor; Golovach, Petr; Jaffke, Lars; Philip, Geevarghese; Sagunov, Danil (Journal article; Peer reviewed, 2020)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 ... 
Diversity of solutions: An exploration through the lens of fixedparameter tractability theory
Baste, Julien; Fellows, Michael Ralph; Jaffke, Lars; Masařík, Tomáš; Oliveira, Mateus De Oliveira; Philip, Geevarghese; Rosamond, Frances (Journal article; Peer reviewed, 2022)When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse ... 
FPT Algorithms for Diverse Collections of Hitting Sets
Baste, Julien; Jaffke, Lars; Masařík, Tomáš; Philip, Geevarghese; Rote, Günter (Peer reviewed; Journal article, 20191127)In this work, we study the dHitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of ... 
MimWidth II. The Feedback Vertex Set Problem
Jaffke, Lars; Kwon, OJoung; Telle, Jan Arne (Peer reviewed; Journal article, 2020)We give a first polynomialtime algorithm for (WEIGHTED) FEEDBACK VERTEX SET on graphs of bounded maximum induced matching width (mimwidth). Explicitly, given a branch decomposition of mimwidth w, we give an nO(w)time ... 
MimWidth III. Graph powers and generalized distance domination problems
Telle, Jan Arne; Jaffke, Lars; Strømme, Torstein Jarl Fagerbakke; Kwon, OJoung (Peer reviewed; Journal article, 2019)We generalize the family of (σ,ρ) problems and locally checkable vertex partition problems to their distance versions, which naturally captures wellknown problems such as Distancer Dominating Set and Distancer Independent ... 
On the Hardness of Generalized Domination Problems Parameterized by MimWidth
Bakkane, Brage I. K.; Jaffke, Lars (Journal article; Peer reviewed, 2022)For nonempty σ, ρ ⊆ ℕ, a vertex set S in a graph G is a (σ, ρ)dominating set if for all v ∈ S, N(v) ∩ S ∈ σ, and for all v ∈ V(G) ⧵ S, N(v) ∩ S ∈ ρ. The Min/Max (σ,ρ)Dominating Set problems ask, given a graph G and ... 
On the maximum number of edges in planar graphs of bounded degree and matching number
Jaffke, Lars; Lima, Paloma T. (Journal article; Peer reviewed, 2023)We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number. 
Structural parameterizations of clique coloring
Jaffke, Lars; Lima, Paloma T.; Philip, Geevarghese (Journal article; Peer reviewed, 2020)A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether ... 
Taming Graphs with No Large Creatures and Skinny Ladders
Gajarský, Jakub; Jaffke, Lars; Lima, Paloma Thome de; Novotná, Jana; Pilipczuk, Marcin; Rzążewski, Paweł; Souza, Uéverton S. (Journal article; Peer reviewed, 2022)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 kcreature as an induced subgraph or a kskinnyladder ... 
Three problems on wellpartitioned chordal graphs
Ahn, Jungho; Jaffke, Lars; Kwon, OJoung; Lima, Paloma Thome de (Journal article; Peer reviewed, 2021)In this work, we solve three problems on wellpartitioned chordal graphs. First, we show that every connected (resp., 2connected) wellpartitioned chordal graph has a vertex that intersects all longest paths (resp., longest ... 
Typical Sequences Revisited  Computing Width Parameters of Graphs
Bodlaender, Hans L.; Jaffke, Lars; Telle, Jan Arne (Journal article; Peer reviewed, 2021)In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized ... 
Typical Sequences Revisited – Computing Width Parameters of Graphs
Bodlaender, Hans L.; Jaffke, Lars; Telle, Jan Arne (Journal article; Peer reviewed, 2020)In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized ... 
A Unifying Framework for Characterizing and Computing Width Measures
Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Jaffke, Lars; Kwon, Ojoung (Journal article; Peer reviewed, 2022)Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or cliquewidth have so far traditionally been tailored to specific width parameters. Moreover, for mimwidth, ... 
Wellpartitioned chordal graphs
Ahn, Jungho; Jaffke, Lars; Kwon, Ojoung; Lima, Paloma T. (Journal article; Peer reviewed, 2022)We introduce a new subclass of chordal graphs that generalizes the class of split graphs, which we call wellpartitioned chordal graphs. A connected graph G is a wellpartitioned chordal graph if there exist a partition P ... 
What Is Known About Vertex Cover Kernelization?
Fellows, Michael R.; Jaffke, Lars; Király, Aliz Izabella; Rosamond, Frances; Weller, Mathias (Peer reviewed; Journal article, 2018)We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkovič on the occasion of his 60th birthday. The Vertex Cover problem is often referred to as the Drosophila of ...