The Gallai vertex problem is Θ₂^p-complete.
Karp , editor =
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
representative citing papers
A harness for AI agents enabled construction of a Rust library with 100+ problem types and 200+ reduction rules for NP-hard problems in three months.
HetRL delivers up to 9.17x higher throughput for LLM RL training on heterogeneous GPUs by using hybrid and ILP-based schedulers to solve a joint optimization problem over computation and data dependencies.
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
Decision problem for minimum interconnection trees in multipartite graphs is NP-complete but FPT in number of parts and polynomial-time on complete, quasi-complete, and t-quasi-complete graphs.
citing papers explorer
-
The Gallai Vertex Problem is $\Theta_2^p$-Complete
The Gallai vertex problem is Θ₂^p-complete.
-
Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems
A harness for AI agents enabled construction of a Rust library with 100+ problem types and 200+ reduction rules for NP-hard problems in three months.
-
HetRL: Efficient Reinforcement Learning for LLMs in Heterogeneous Environments
HetRL delivers up to 9.17x higher throughput for LLM RL training on heterogeneous GPUs by using hybrid and ILP-based schedulers to solve a joint optimization problem over computation and data dependencies.
-
Hardness and Approximation for Coloring Digraphs
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
-
Complexity of Finding and Enumerating Interconnection Trees
Decision problem for minimum interconnection trees in multipartite graphs is NP-complete but FPT in number of parts and polynomial-time on complete, quasi-complete, and t-quasi-complete graphs.