Cover Image

The Gallai Vertex Problem is $Θ_2^p$-Complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nikabadi, Amir, Rotenberg, Eva, Wulf, Lasse
Format:	Preprint
Published:	2026
Subjects:	Discrete Mathematics Computational Complexity 68Q25, 05C38, 05D15, 05C69, 68R01, 68Q15 F.2.2; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

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

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

DAG Scheduling in the BSP Model
by: Papp, Pál András, et al.
Published: (2023)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
by: Komusiewicz, Christian, et al.
Published: (2023)

Approximating branchwidth on parametric extensions of planarity
by: Thilikos, Dimitrios M., et al.
Published: (2023)

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

A Theory for Coloring Walks in a Digraph
by: Chaiken, Seth
Published: (2024)

Computing shortest closed curves on non-orientable surfaces
by: Bulavka, Denys, et al.
Published: (2024)

Folding One Polyhedral Metric Graph into Another
by: Chung, Lily, et al.
Published: (2024)

Packing, Hitting, and Colouring Squares
by: Caoduro, Marco, et al.
Published: (2022)

Quickly excluding an annotated planar graph
by: Gorsky, Maximilian, et al.
Published: (2026)

The price of homogeneity is polynomial
by: Gorsky, Maximilian, et al.
Published: (2026)

On (In)approximability of MaxMin Independent Set Reconfiguration
by: Hoang, Hung P., et al.
Published: (2026)

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

Optimal Bounds for the k-Disjoint Paths Problem
by: Cavallaro, Dario, et al.
Published: (2026)

A New Temporal Interpretation of Cluster Editing
by: Bocci, Cristiano, et al.
Published: (2022)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

Backbone coloring for graphs with degree 4
by: Michalik, Krzysztof, et al.
Published: (2024)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

Vertex identification to a forest
by: Morelle, Laure, et al.
Published: (2024)

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

Degree-preserving graph dynamics -- a versatile process to construct random networks
by: Erdős, Péter L., et al.
Published: (2021)

Catching Rats in $H$-minor-free Graphs
by: Gorsky, Maximilian, et al.
Published: (2025)

Completely independent spanning trees in the hypercube
by: Shaw, Benedict Randall
Published: (2024)

Adjacent vertex distinguishing total coloring of 3-degenerate graphs
by: Behera, Diptimaya, et al.
Published: (2025)

Results on three problems on isolation of graphs
by: Borg, Peter, et al.
Published: (2026)

Amnesiac Flooding: Easy to break, hard to escape
by: Austin, Henry, et al.
Published: (2025)

Topological Indices With Degree Sequence $\mathscr{D}$ of Tree
by: Hamoud, Jasem, et al.
Published: (2025)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
by: Demaine, Erik D., et al.
Published: (2024)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
by: Lobe, Elisabeth, et al.
Published: (2021)

Irregularity and Topological Indices in Fibonacci Word Trees and Modified Fibonacci Word Index
by: Hamoud, Jasem, et al.
Published: (2025)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
by: Philip, Geevarghese, et al.
Published: (2026)

State Canonization and Early Pruning in Width-Based Automated Theorem Proving
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
by: Gabryelski, Wojciech, et al.
Published: (2026)

Counting Kernels in Directed Graphs with Arbitrary Orientations
by: Jartoux, Bruno
Published: (2022)

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

Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points
by: Rose, Valentino Delle, et al.
Published: (2023)

Bell Numbers and Stirling Numbers of the Mycielskian of Trees
by: Allagan, J., et al.
Published: (2025)