The Gallai vertex problem is Θ₂^p-complete.
Karp , editor =
7 Pith papers cite this work, alongside 2,794 external citations. Polarity classification is still indexing.
7
Pith papers citing it
2,794
external citations · OpenAlex
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.
Closes the missing direction of an open question on incomparability of two induction theories via a short syntactic argument and extracts the Syntactic Invariance Principle.
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.
A Transformer model trained via supervised learning on ILP solutions for a new nursing care taxi dispatch VRP variant reduces operating time by up to 8% on small instances while keeping constraint violations low.
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.
-
Syntactic Systems Cannot See Semantic Invariants
Closes the missing direction of an open question on incomparability of two induction theories via a short syntactic argument and extracts the Syntactic Invariance Principle.
-
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.
-
Optimizing Nursing Care Taxi Dispatch Leveraging Integer Linear Programming Solvers and Machine Learning
A Transformer model trained via supervised learning on ILP solutions for a new nursing care taxi dispatch VRP variant reduces operating time by up to 8% on small instances while keeping constraint violations low.