Cover Image

Thin Tree Verification is coNP-Complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Moayyedi, Alice
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity 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

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
by: Fairbairn, David L., et al.
Published: (2024)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
by: Kiatchaipipat, Nattapol, et al.
Published: (2025)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
by: Knop, Dušan, et al.
Published: (2017)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

On Minimum Maximal Distance-k Matchings
by: Kartynnik, Yury, et al.
Published: (2016)

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Realizing temporal graphs from fastest travel times
by: Klobas, Nina, et al.
Published: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
by: Clinch, Katie, et al.
Published: (2024)

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

Complexity of Firefighting on Graphs
by: Althoetmar, Julius, et al.
Published: (2025)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
by: Bok, Jan, et al.
Published: (2025)

Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework
by: Lee, Changryeol
Published: (2026)

Large cliques and large independent sets: can they coexist?
by: Feige, Uriel, et al.
Published: (2025)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
by: Kowaluk, Miroslaw, et al.
Published: (2025)

Direct Sums for Parity Decision Trees
by: Besselman, Tyler, et al.
Published: (2024)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
by: Gupta, Chetan, et al.
Published: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
by: Fritsch, Timo, et al.
Published: (2026)

Fast Simulation of Cellular Automata by Self-Composition
by: Natal, Joseph, et al.
Published: (2024)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

The characteristic polynomials of $r$-uniform hypercycles with length $l$
by: Bo, Dong, et al.
Published: (2025)

On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
by: Diaby, Moustapha, et al.
Published: (2023)

Kernelization dichotomies for hitting minors under structural parameterizations
by: Bougeret, Marin, et al.
Published: (2025)

Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
by: Bougeret, Marin, et al.
Published: (2024)

When Votes Change and Committees Should (Not)
by: Bredereck, Robert, et al.
Published: (2020)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
by: Liao, Chao, et al.
Published: (2022)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
by: Istrate, Gabriel
Published: (2024)

Two-Sided Lossless Expanders in the Unbalanced Setting
by: Chattopadhyay, Eshan, et al.
Published: (2024)

Drawing Reeb Graphs
by: Chambers, Erin, et al.
Published: (2025)

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

On the complexity of Sandwich Problems for $M$-partitions
by: Barsukov, Alexey, et al.
Published: (2026)

Proper colorings of a graph in linear time using a number of colors linear in the maximum degree of the graph
by: Bhandari, Kritika, et al.
Published: (2025)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
by: Lingas, Andrzej
Published: (2026)

On the Hardness of the One-Sided Code Sparsifier Problem
by: Grigorescu, Elena, et al.
Published: (2025)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
by: van Brügge, Jan
Published: (2024)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
by: Grüne, Christoph, et al.
Published: (2023)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
by: Burke, Kyle, et al.
Published: (2024)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
by: Bartlett, Celina Janet
Published: (2025)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
by: Lagerkvist, Victor, et al.
Published: (2025)