:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bodlaender, Hans L., Groenland, Carla, Jacob, Hugo, Pilipczuk, Marcin, Pilipczuk, Michał
Format:	Preprint
Published:	2022
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2206.11828
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
by: Pilipczuk, Michał, et al.
Published: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

XALP-completeness of Parameterized Problems on Planar Graphs
by: Bodlaender, Hans L., et al.
Published: (2024)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
by: Bodlaender, Hans L., et al.
Published: (2026)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
by: Vroon, Mats, et al.
Published: (2025)

On the parameterized complexity of computing tree-partitions
by: Bodlaender, Hans L., et al.
Published: (2022)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

Trade-off between spread and width for tree decompositions
by: Bodlaender, Hans L., et al.
Published: (2026)

Hedonic Seat Arrangement Problems
by: Bodlaender, Hans L., et al.
Published: (2020)

Faster diameter computation in graphs of bounded Euler genus
by: Kluk, Kacper, et al.
Published: (2025)

Concurrency Constrained Scheduling with Tree-Like Constraints
by: Bodlaender, Hans L., et al.
Published: (2025)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
by: Gartland, Peter, et al.
Published: (2023)

Strong odd colorings in graph classes of bounded expansion
by: Pilipczuk, Michał
Published: (2025)

Parameterized and approximation algorithms for coverings points with segments in the plane
by: Kowalska, Katarzyna, et al.
Published: (2024)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
by: Hörsch, Florian, et al.
Published: (2025)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
by: Przybyłek, Michał R., et al.
Published: (2026)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
by: Chudigiewitsch, Florian, et al.
Published: (2026)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities
by: Makowski, Michał
Published: (2024)

On the Complexity of Target Set Selection in Simple Geometric Networks
by: Dvořák, Michal, et al.
Published: (2023)

Parameterized Complexity of the Star Decomposition Problem
by: Hajebi, Sahab, et al.
Published: (2024)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

On the Exact Matching Problem in Dense Graphs
by: Maalouly, Nicolas El, et al.
Published: (2024)

On coarse tree decompositions and coarse balanced separators
by: Abrishami, Tara, et al.
Published: (2025)

Complexity Thresholds for the Constrained Colored Token Swapping Problem
by: Bilò, Davide, et al.
Published: (2026)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

The Parameterized Complexity of Coloring Mixed Graphs
by: Lauerbach, Antonio, et al.
Published: (2026)

Hexasort -- The Complexity of Stacking Colors on Graphs
by: Klocker, Linus, et al.
Published: (2026)

On the Complexity of Vertex-Splitting Into an Interval Graph
by: Abu-Khzam, Faisal N., et al.
Published: (2026)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)