Structural parameterizations for two bounded degree problems revisited
M Lampis, M Vasilakis - ACM Transactions on Computation Theory, 2024 - dl.acm.org
We revisit two well-studied problems, Bounded Degree Vertex Deletion and Defective
Coloring, where the input is a graph G and a target degree Δ, and we are asked either to edit …
Coloring, where the input is a graph G and a target degree Δ, and we are asked either to edit …
Tight algorithms for connectivity problems parameterized by clique-width
F Hegerfeld, S Kratsch - arXiv preprint arXiv:2302.03627, 2023 - arxiv.org
The complexity of problems involving global constraints is usually much more difficult to
understand than the complexity of problems only involving local constraints. A natural form …
understand than the complexity of problems only involving local constraints. A natural form …
Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters
A homomorphism from a graph $ G $ to a graph $ H $ is an edge-preserving mapping from $
V (G) $ to $ V (H) $. In the graph homomorphism problem, denoted by $ Hom (H) $, the …
V (G) $ to $ V (H) $. In the graph homomorphism problem, denoted by $ Hom (H) $, the …
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
It is known for many algorithmic problems that if a tree decomposition of width $ t $ is given
in the input, then the problem can be solved with exponential dependence on $ t $. A line of …
in the input, then the problem can be solved with exponential dependence on $ t $. A line of …
Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters
C Groenland, I Mannens, J Nederlof… - 51st International …, 2024 - drops.dagstuhl.de
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V (G) to
V (H). In the graph homomorphism problem, denoted by Hom (H), the graph H is fixed and …
V (H). In the graph homomorphism problem, denoted by Hom (H), the graph H is fixed and …
Hitting Meets Packing: How Hard Can it Be?
We study a general family of problems that form a common generalization of classic hitting
(also referred to as covering or transversal) and packing problems. An instance of X-HitPack …
(also referred to as covering or transversal) and packing problems. An instance of X-HitPack …
The Primal Pathwidth SETH
M Lampis - arXiv preprint arXiv:2403.07239, 2024 - arxiv.org
Motivated by the importance of dynamic programming (DP) in parameterized complexity, we
consider several fine-grained questions, such as the following examples:(i) can Dominating …
consider several fine-grained questions, such as the following examples:(i) can Dominating …
Circuits and Backdoors: Five Shades of the SETH
M Lampis - arXiv preprint arXiv:2407.09683, 2024 - arxiv.org
The SETH is a hypothesis of fundamental importance to (fine-grained) parameterized
complexity theory and many important tight lower bounds are based on it. This situation is …
complexity theory and many important tight lower bounds are based on it. This situation is …
Tight algorithmic applications of clique-width generalizations
V Chekan, S Kratsch - arXiv preprint arXiv:2307.04628, 2023 - arxiv.org
In this work, we study two natural generalizations of clique-width introduced by Martin F\"
urer. Multi-clique-width (mcw) allows every vertex to hold multiple labels [ITCS 2017], while …
urer. Multi-clique-width (mcw) allows every vertex to hold multiple labels [ITCS 2017], while …
A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
N Bojikian, S Kratsch - arXiv preprint arXiv:2307.14264, 2023 - arxiv.org
Recently, Hegerfeld and Kratsch [ESA 2023] obtained the first tight algorithmic results for
hard connectivity problems parameterized by clique-width. Concretely, they gave one-sided …
hard connectivity problems parameterized by clique-width. Concretely, they gave one-sided …