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

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 ... 
bColoring Parameterized by CliqueWidth
Jaffke, Lars; Lima, Paloma T.; Lokshtanov, Daniel (Journal article; Peer reviewed, 2023)We provide a polynomialtime algorithm for b Coloring on graphs of constant cliquewidth. This unifies and extends nearly all previously known polynomial time 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 ... 
Classes of intersection digraphs with good algorithmic properties
Jaffke, Lars; Kwon, Ojoung; Telle, Jan Arne (Journal article; Peer reviewed, 2023)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 ... 
Dynamic Programming on Bipartite Tree Decompositions
Jaffke, Lars; Morelle, Laure; Sau, Ignasi; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of ... 
Finegrained parameterized complexity analysis of graph coloring problems
Jaffke, Lars; Jansen, Bart Maarten Paul (Journal article; Peer reviewed, 2023)The qColoring problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a finegrained analysis of the complexity of q Coloring with respect to a hierarchy of structural ... 
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 bColoring
Jaffke, Lars; Lima, Paloma Thome de; Sharma, Roohani (Journal article; Peer reviewed, 2023)The bColoring problem, which given a graph G and an integer k asks whether G has a proper kcoloring such that each color class has a vertex adjacent to all color classes except its own, is known to be FPT parameterized ... 
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 ...