Browsing Department of Informatics by Author "Jaffke, Lars"
Now showing items 113 of 13

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 ... 
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 ... 
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 ... 
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 ... 
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 ... 
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 ...