:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Klocker, Linus, Fink, Simon D.
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2603.01244
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Hardness of clique approximation for monotone circuits
by: Błasiok, Jarosław, et al.
Published: (2025)

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

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

Pathways to Tractability for Geometric Thickness
by: Depian, Thomas, et al.
Published: (2024)

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

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

Block Stacking, Airplane Refueling, and Robust Appointment Scheduling
by: Gmeiner, Simon, et al.
Published: (2026)

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
by: Liu, Brian, et al.
Published: (2024)

The Complexity of Contracting Bipartite Graphs into Small Cycles
by: Krithika, R., et al.
Published: (2022)

On the Parameterized Complexity of Semitotal Domination on Graph Classes
by: Retschmeier, Lukas
Published: (2025)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
by: Mackenzie, Simon, et al.
Published: (2024)

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

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
by: Komarath, Balagopal, et al.
Published: (2025)

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

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

The Complexity of Drawing Graphs on Few Lines and Few Planes
by: Chaplick, Steven, et al.
Published: (2016)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
by: MIT Hardness Group, et al.
Published: (2024)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

Parameterised Complexity of Consistent Query Answering via Graph Representations
by: Hankala, Teemu, et al.
Published: (2024)

Quantum Circuit Optimization by Graph Coloring
by: Lee, Hochang, et al.
Published: (2025)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Mistake-bounded online learning with operation caps
by: Geneson, Jesse, et al.
Published: (2025)

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

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

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

The Descriptive Complexity of Graph Neural Networks
by: Grohe, Martin
Published: (2023)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

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

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

NP-Completeness of Neighborhood Balanced Colorings
by: Asaeedi, Saeed
Published: (2024)

Structure in Communication Complexity and Constant-Cost Complexity Classes
by: Hatami, Hamed, et al.
Published: (2024)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

A Structural Complexity Analysis of Hierarchical Task Network Planning
by: Brand, Cornelius, et al.
Published: (2024)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
by: Borzechowski, Michaela, et al.
Published: (2024)

Modelling Network Resilience: The Complexity of Some Graph Division Games
by: Gutowski, Grzegorz, et al.
Published: (2026)