Buchumschlag

XALP-completeness of Parameterized Problems on Planar Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bodlaender, Hans L., Szilágyi, Krisztina
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity 05C10, 68Q15 G.2.2
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Gallai Vertex Problem is $Θ_2^p$-Complete
von: Nikabadi, Amir, et al.
Veröffentlicht: (2026)

Graph polynomials: some questions on the edge
von: Farr, Graham, et al.
Veröffentlicht: (2024)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
von: Lobe, Elisabeth, et al.
Veröffentlicht: (2021)

Computing shortest closed curves on non-orientable surfaces
von: Bulavka, Denys, et al.
Veröffentlicht: (2024)

DAG Scheduling in the BSP Model
von: Papp, Pál András, et al.
Veröffentlicht: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
von: Levet, Michael, et al.
Veröffentlicht: (2023)

Folding One Polyhedral Metric Graph into Another
von: Chung, Lily, et al.
Veröffentlicht: (2024)

Logarithmic Weisfeiler--Leman and Treewidth
von: Levet, Michael, et al.
Veröffentlicht: (2023)

On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum
von: Ameli, Afrouz Jabal, et al.
Veröffentlicht: (2024)

State Canonization and Early Pruning in Width-Based Automated Theorem Proving
von: Oliveira, Mateus de Oliveira, et al.
Veröffentlicht: (2026)

Identification to Subclasses of Chordal Graphs
von: Golovach, Petr A., et al.
Veröffentlicht: (2026)

Evolomino is NP-complete
von: Nikolaev, Andrei V.
Veröffentlicht: (2025)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
von: Bannach, Max, et al.
Veröffentlicht: (2025)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
von: Chen, Yijia, et al.
Veröffentlicht: (2023)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
von: Calamoneri, Tiziana, et al.
Veröffentlicht: (2025)

On the complexity of Sandwich Problems for $M$-partitions
von: Barsukov, Alexey, et al.
Veröffentlicht: (2026)

A New Temporal Interpretation of Cluster Editing
von: Bocci, Cristiano, et al.
Veröffentlicht: (2022)

The Word Problem for Products of Symmetric Groups
von: Simon, Hans U.
Veröffentlicht: (2025)

Dichotomy for orderings?
von: Kun, Gábor, et al.
Veröffentlicht: (2025)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
von: Demaine, Erik D., et al.
Veröffentlicht: (2024)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
von: Emmerich, Michael T. M., et al.
Veröffentlicht: (2026)

The Optimizer Quotient and the Certification Trilemma
von: Simas, Tristan
Veröffentlicht: (2026)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
von: Abdullah, Duaa, et al.
Veröffentlicht: (2025)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
von: Morse, Gregory, et al.
Veröffentlicht: (2026)

On Grundy indices for complete geometric graphs
von: Lara, Dolores, et al.
Veröffentlicht: (2025)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
von: Calamoneri, Tiziana, et al.
Veröffentlicht: (2025)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
von: Golovach, Petr A., et al.
Veröffentlicht: (2022)

Graphs whose vertices of degree at least 2 lie in a triangle
von: Forte, Vinicius L. do, et al.
Veröffentlicht: (2022)

Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach
von: Chimani, Markus, et al.
Veröffentlicht: (2024)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
von: Ahn, Jungho, et al.
Veröffentlicht: (2022)

Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
von: Nederlof, Jesper, et al.
Veröffentlicht: (2023)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
von: Jain, Rahul, et al.
Veröffentlicht: (2019)

Approximating branchwidth on parametric extensions of planarity
von: Thilikos, Dimitrios M., et al.
Veröffentlicht: (2023)

Graph covers and semi-covers: Who is stronger?
von: Kratochvil, Jan, et al.
Veröffentlicht: (2025)

Dominic Welsh: his work and influence
von: Farr, Graham, et al.
Veröffentlicht: (2024)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
von: Lela, Marko
Veröffentlicht: (2025)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
von: Philip, Geevarghese, et al.
Veröffentlicht: (2026)

Vertex identification to a forest
von: Morelle, Laure, et al.
Veröffentlicht: (2024)

Faster parameterized algorithms for modification problems to minor-closed classes
von: Morelle, Laure, et al.
Veröffentlicht: (2022)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
von: Komusiewicz, Christian, et al.
Veröffentlicht: (2023)