2025/11/06 by Christoph Grüne, Grüne, Christoph, Femke Pfaue +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2511.04308
openalex publication_date 2025/11/06 · openalex created_date 2025/11/08 · openalex updated_date 2026/07/28
The website reductions.network serves as a comprehensive database for exploring problems and reductions between them. It presents several complexity classes in the form of an interconnected graph where problems are represented as vertices, while edges represent reductions between them. This graphical perspective allows for identifying problem clusters and simplifying finding problem candidates to reduce from. Moreover, users can easily search for existing problems via a dedicated search bar, and various filters allow them to focus on specific subgraphs of interest. The design of the website enables users to contribute by adding new problems and reductions to the database. Furthermore, the software architecture allows for the integration of additional graphs corresponding to new complexity classes. In the current state, the following networks with their respective complexity classes are included: - classical complexity including the classes NP, #P, and SSP-NP - parameterized complexity including the classes W[1], W[2] - gap-preserving reductions under the PCP-Theorem and the Unique Games Conjecture.