Reductions

A reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.

Reductions Table

Displaying 319 of 319 reductions


Double 3-Term Arithmetic Progression	Convolution 3SUM	2025
Exact Triangle	Edge Triangle Detection	2024
3SUM	Set Disjointness	2023
3SUM	Set Intersection	2023
Convolution 3SUM	Convolution Witness	2023
3SUM	Mono Convolution	2023
3SUM'	#3SUM	2023
#3SUM	3SUM'	2023
Convolution 3SUM	#Convolution-3SUM	2023
#Convolution-3SUM	Convolution 3SUM	2023
All-Integers 3SUM	Dynamic $k$-Mismatch	2022
3SUM	1-Partite 4-variate Linear Degeneracy Testing, Non-Trivial	2022
Triangle Listing	Approximate Distance Oracle	2022
Triangle Listing	4-Cycle Listing	2022
OV	Longest Common Substring with don't cares	2022
Conjunctive Normal Form SAT	Subset Sum	2022
All-Reals 3SUM	Edge Triangle Detection	2022
Real All-Edges Exact Triangle	Edge Triangle Detection	2022
APSP on Directed Graphs with Real-Valued Weights	Edge Triangle Detection	2022
All-Reals 3SUM	Edge Triangle Counting	2022
#Real All-Edges Exact Triangle	Edge Triangle Counting	2022
Real 3SUM	All-Edges Monochromatic Triangle	2022
Real Exact Triangle	All-Edges Monochromatic Triangle	2022
APSP on Directed Graphs with Real-Valued Weights	All-Edges Monochromatic Triangle	2022
#Real All-Edges Exact Triangle	#All-Edges Monochromatic Triangle	2022
Real 3SUM	#All-Edges Monochromatic Triangle	2022
APSP on Directed Graphs with Real-Valued Weights	Colorful Boolean Matrix Multiplication	2022
OV	Colorful Boolean Matrix Multiplication	2022
All-Color-Pairs Triangle Collection*	All-Color-Pairs Triangle Collection	2022
Triangle Collection	Triangle Collection*	2022
All-Color-Pairs Triangle Collection	All-Color-Pairs Triangle Collection*	2022
All-Edges Monochromatic Triangle	All-Color-Pairs Triangle Collection*	2022
Colorful Boolean Matrix Multiplication	All-Color-Pairs Triangle Collection	2022
OV	Triangle Collection*	2022
Edge Triangle Detection	All-Edges Monochromatic Triangle	2022
All-Edges Monochromatic Triangle	All-Edges Exact Triangle	2022
Real 3SUM	Real Exact Triangle	2022
Convolution 3SUM	Point Hausdorff Distance under Translation	2021
Convolution 3SUM	Double 3-Term Arithmetic Progression	2021
Double 3-Term Arithmetic Progression	Additive Square Factor Detection in Integer Strings	2021
Double 3-Term Arithmetic Progression	Abelian Square Factor Centers Enumeration	2021
Double 3-Term Arithmetic Progression	Odd Abelian Square Factor Detection	2021
k-OV	Diameter k vs 2k-1	2021
OV	Partial Match	2020
Partial Match	Subset Query	2020
Subset Query	OV	2020
3SUM	Convolution 3SUM	2020
Convolution 3SUM	3SUM	2020
3SUM	1-Partite 3-variate Linear Degeneracy Testing, Non-Trivial	2020
1-Partite 3-variate Linear Degeneracy Testing, Non-Trivial	3SUM	2020
3SUM'	3-Partite 3-variate Linear Degeneracy Testing, Non-Trivial	2020
3-Partite 3-variate Linear Degeneracy Testing, Non-Trivial	3SUM'	2020
3-Partite 3-variate Linear Degeneracy Testing, Non-Trivial	1-Partite 3-variate Linear Degeneracy Testing, Non-Trivial	2020
1-Partite 3-variate Linear Degeneracy Testing, Non-Trivial	3-Partite 3-variate Linear Degeneracy Testing, Non-Trivial	2020
3SUM	Grammar-Compressed Vector Inner Product	2020
3SUM	Grammar-Compressed Square-Matrix-Vector Multiplication	2020
3SUM	All-Edges Monochromatic Triangle	2020
Mono Convolution	3SUM	2020
All-Edges Monochromatic Triangle	Edge Triangle Detection	2020
(min, +) Convolution	Smallest k-Enclosing Rectangle	2019
(min, +) Convolution	Min-Weight k-Enclosing Rectangle	2019
Convolution 3SUM	Closest-Weight k-Enclosing Rectangle	2019
Triangle Listing	Dynamic Vertex Triangle Listing	2019
Dynamic Vertex Triangle Listing	Induced Subgraph Problem	2019
Dictionary Matching with One Gap*	Induced Subgraph Problem	2019
Induced Subgraph Problem	Dictionary Matching with One Gap*	2019
Dictionary Matching with One Gap*	Dictionary Matching with One Gap	2019
Directed, Weighted APSP	Negative Triangle Detection	2018
Directed, Weighted APSP	Exact Triangle	2018
Negative Triangle Detection	Distance Product Verification	2018
Distance Product Verification	Distance Product	2018
Distance Product	Negative Triangle Detection	2018
Negative Triangle Search	Negative Triangle Detection	2018
Negative Triangle Listing	Negative Triangle Detection	2018
Distance Product	Negative Triangle Detection	2018
Distance Product	Negative Triangle Detection	2018
Distance Product	Negative Triangle Detection	2018
Minimum Witness Finding	Negative Triangle Detection	2018
All Pairs Minimum Witness (APMW)	Negative Triangle Detection	2018
Undirected, Weighted APSP	Directed, Weighted APSP	2018
Directed, Weighted APSP	Undirected, Weighted APSP	2018
Metricity	Negative Triangle Detection	2018
Negative Triangle Detection	Metricity	2018
Negative Triangle Detection	Shortest Cycle	2018
Negative Triangle Detection	2D Maximum Subarray	2018
Second Shortest Simple Path	Directed, Weighted APSP	2018
Replacement Paths Problem (RPP)	Directed, Weighted APSP	2018
Minimum Weight Triangle	Second Shortest Simple Path	2018
Distance Product	Second Shortest Simple Path	2018
Directed, Weighted APSP	Second Shortest Simple Path	2018
Directed, Weighted APSP	Replacement Paths Problem (RPP)	2018
Combinatorial Triangle Detection	Independent Set Queries	2018
Combinatorial BMM	Independent Set Queries	2018
Negative Triangle Detection	Price Query	2018
Nondecreasing Triangle	Triangle in Unweighted Graph	2018
$(\min, \leq)$ Product	Triangle in Unweighted Graph	2018
All-Integers 3SUM	3SUM	2018
3SUM	All-Integers 3SUM	2018
Min-Weight k-Clique	Min-Weight k-Cycle	2018
Min-Weight k-Cycle	Undirected Wiener Index	2018
MaxSAT	st-Maximum Flow	2018
MaxSAT	All-Pairs Maximum Flow	2018
MaxSAT	All-Pairs Maximum Flow	2018
MaxSAT	st-Maximum Flow	2018
MaxSAT	Maximum Local Edge Connectivity	2018
OV	Subtree Isomorphism	2018
OV	Largest Common Subtree	2018
Combinatorial Triangle Detection	Combinatorial BMM	2018
Combinatorial BMM	Combinatorial Triangle Detection	2018
(max, +) Convolution Lower Bound Testing	$\ell_\infty$ Necklace Alignment	2017
(min, +) Convolution	(max, +) Convolution Upper Bound Testing	2017
(max, +) Convolution Upper Bound Testing	Superadditivity Testing	2017
Superadditivity Testing	Unbounded Knapsack	2017
Unbounded Knapsack	0-1 Knapsack	2017
0-1 Knapsack	(min, +) Convolution	2017
(min, +) Convolution	Tree Sparsity	2017
Tree Sparsity	(min, +) Convolution	2017
(max, +) Convolution Upper Bound Testing	Convolution 3SUM	2017
Combinatorial BMM	2-sensitive incremental st-reach	2017
Combinatorial BMM	1-sensitive incremental ss-reach	2017
Combinatorial BMM	ap-reach	2017
Combinatorial BMM	2-sensitive (7/5)-approximate st-shortest paths	2017
Combinatorial BMM	1-sensitive (3/2)-approximate ss-shortest paths	2017
Combinatorial BMM	(5/3)-approximate ap-shortest paths	2017
Combinatorial BMM	1-sensitive (4/3)-approximate decremental diameter	2017
Combinatorial BMM	1-sensitive (4/3)-approximate decremental eccentricity	2017
Combinatorial BMM	1-sensitive decremental st-shortest paths	2017
Replacement Paths Problem (RPP)	1-sensitive decremental st-shortest paths	2017
Directed, Weighted APSP	2-sensitive decremental st-shortest paths	2017
Directed, Weighted APSP	1-sensitive decremental diameter	2017
Conjunctive Normal Form SAT	sensitive incremental #SSR	2017
Conjunctive Normal Form SAT	constant sensitivity (4/3)-approximate incremental diameter	2017
Conjunctive Normal Form SAT	sensitive incremental ST-Reach	2017
k-Clique	CFG Recognition	2017
k-Clique	RNA Folding	2017
k-Clique	CFG Recognition	2017
k-Clique	RNA Folding	2017
Bichromatic Hamming Close Pair	Approximate Hard-Margin SVM	2017
Set Disjointness	Edge Triangle Counting	2016
Set Intersection	Triangle Listing	2016
Convolution Witness	Partial Convolution	2016
Convolution Witness	Partial Convolution Indexing	2016
Convolution Witness	Partial Matrix Multiplication	2016
Convolution Witness	Partial Matrix Multiplication Indexing	2016
Online Vector-Matrix-Vector Multiplication	Bipartite Graph MCM	2016
Conjunctive Normal Form SAT	dynamic st-Maximum Flow	2016
Online Vector-Matrix-Vector Multiplication	dynamic st-Maximum Flow	2016
Triangle Collection*	Dynamic 4/3-Diameter	2016
Triangle Collection*	Dynamic 4/3-Diameter	2016
Triangle Collection*	Dynamic 4/3-Diameter	2016
Combinatorial Triangle Detection	Disjunctive coBüchi Objectives	2016
OV	Generalized Büchi Games	2016
Combinatorial Triangle Detection	Disjunctive Reachability Queries in MDPs	2016
OV	Disjunctive Reachability Queries in MDPs	2016
Combinatorial Triangle Detection	Disjunctive Queries of Safety in Graphs	2016
OV	Disjunctive Queries of Safety in Graphs	2016
OV	Maximum Inner Product Search	2016
Maximum Inner Product Search	Boolean d-Attribute Stable Matching	2016
Maximum Inner Product Search	Stable Matching Verification	2016
Maximum Inner Product Search	Stable Pair Checking	2016
Maximum Inner Product Search	Stable Pair Checking	2016
Maximum Inner Product Search	Stable Pair Checking	2016
Max-Weight k-Clique	Max-Weight Rectangle	2016
Negative Triangle Detection	2D Maximum Subarray	2016
Undirected, Weighted APSP	2D Maximum Subarray	2016
Max-Weight k-Clique	dD Maximum Subarray	2016
Max-Weight k-Clique	dD Maximum Square Subarray	2016
Max-Weight k-Clique	Weighted Depth	2016
MaxSAT	Most OV	2015
Most OV	Longest Common Subsequence	2015
Unbalanced OV	Dynamic Time Warping	2015
Unbalanced OV	Longest Common Subsequence	2015
Exact Triangle	$\Delta$-Matching Triangles	2015
Exact Triangle	Triangle Collection*	2015
Triangle Collection*	Triangle Collection	2015
Triangle Listing	"Exists" Connectivity in Graph Timelines	2015
Triangle Detection	"Exists" Connectivity in Graph Timelines	2015
Conjunctive Normal Form SAT	Triangle Collection*	2015
Directed Radius	Directed, Weighted APSP	2015
Undirected Radius	Undirected, Weighted APSP	2015
Directed Median	Directed, Weighted APSP	2015
Undirected Median	Undirected, Weighted APSP	2015
Betweenness Centrality (BC)	Directed, Weighted APSP	2015
Betweenness Centrality (BC)	Undirected, Weighted APSP	2015
Negative Triangle Detection	Betweenness Centrality (BC)	2015
Negative Triangle Detection	Directed Radius	2015
Negative Triangle Detection	Undirected Radius	2015
Negative Triangle Detection	Directed Median	2015
Negative Triangle Detection	Undirected Median	2015
Negative Triangle Detection	All-Nodes Median Parity	2015
Directed, Weighted APSP	All-Nodes Median Parity	2015
Undirected, Weighted APSP	All-Nodes Median Parity	2015
Diameter	Reach Centrality	2015
Reach Centrality	Diameter	2015
Diameter	Positive Betweenness Centrality	2015
Positive Betweenness Centrality	Diameter	2015
Reach Centrality	Positive Betweenness Centrality	2015
Negative Triangle Detection	Directed All-Nodes Positive Betweenness Centrality	2015
Negative Triangle Detection	Undirected All-Nodes Positive Betweenness Centrality	2015
Directed, Weighted APSP	Directed All-Nodes Positive Betweenness Centrality	2015
Undirected, Weighted APSP	Undirected All-Nodes Positive Betweenness Centrality	2015
Directed, Weighted APSP	Directed All-Nodes Reach Centrality	2015
Undirected, Weighted APSP	Undirected All-Nodes Reach Centrality	2015
Diameter	Approximate Betweenness Centrality	2015
Approximate Betweenness Centrality	Diameter	2015
Diameter	Undirected, Weighted APSP	2015
Conjunctive Normal Form SAT	Positive [1, 2] Betweenness Centrality	2015
Conjunctive Normal Form SAT	Approximate Betweenness Centrality	2015
Conjunctive Normal Form SAT	Approximate Reach Centrality	2015
Conjunctive Normal Form SAT	Approximate Reach Centrality	2015
OV	Bichromatic Hamming Close Pair	2015
OV	Edit Distance	2014
Conjunctive Normal Form SAT	Frechet Distance	2014
3SUM	Local Alignment	2014
Convolution 3SUM	Jumbled Indexing	2014
Conjunctive Normal Form SAT	Local Alignment	2014
Conjunctive Normal Form SAT	Longest Common Substring with don't cares	2014
Conjunctive Normal Form SAT	Multiple Local Alignment	2014
Local Alignment	Multiple Local Alignment	2014
Max-Weight k-Clique	Multiple Local Alignment	2014
Max-Weight 4-Clique	Local Alignment	2014
(min, +) Convolution	Maximum Consecutive Subsums	2014
Maximum Consecutive Subsums	(min, +) Convolution	2014
Conjunctive Normal Form SAT	#SSR	2014
Conjunctive Normal Form SAT	2 Strong Components (dynamic)	2014
Conjunctive Normal Form SAT	Dynamic MaxSCC	2014
Conjunctive Normal Form SAT	Dynamic Connected Subgraph	2014
Conjunctive Normal Form SAT	Dynamic 4/3-Diameter	2014
Conjunctive Normal Form SAT	Dynamic ST-Reach	2014
Triangle Detection	Dynamic ST-Reach	2014
Triangle Detection	Dynamic Strong Connectivity	2014
Triangle Detection	Dynamic Bipartite Maximum-Weight Matching	2014
Directed, Weighted APSP	Dynamic $st$-Shortest Path	2014
Directed, Weighted APSP	Dynamic Bipartite Maximum-Weight Matching	2014
OV	Diameter 2 vs 3	2013
Convolution 3SUM	Exact Triangle	2013
3SUM	Exact Weight 3-Star Detection	2013
3SUM	Exact Weight 3-Matching Detection	2013
Exact Weight 3-Star Detection	Exact Weight 3-Matching Detection	2013
Exact Weight 3-Star Detection	3SUM	2013
Exact Weight 3-Matching Detection	Exact Weight 3-Star Detection	2013
Exact Weight 3-Matching Detection	3SUM	2013
Conjunctive Normal Form SAT	Approximate Diameter	2013
Triangle Listing	3SUM	2013
Triangle Listing	Triangle Detection	2013
Edge Triangle Detection	All-Integers 3SUM	2013
(min, +) Convolution	Distance Product	2012
$\ell_\infty$ Necklace Alignment	(min, +) Convolution	2012
$\ell_1$ Necklace Alignment	(median, +) Convolution	2012
3SUM	Pattern Distance, Normalized Hamming Distance under Shifts	2011
Geometric Base	Pattern Distance, Normalized Hamming Distance under Shifts and Scaling	2011
Shortest Cycle	Minimum Weight Triangle	2011
Minimum Weight Triangle	Shortest Cycle	2011
Convolution 3SUM	Triangle Listing	2010
Point on 3 Lines	Max Depth	2008
Point on 3 Lines	Approximate Max-Area Visible Polygon	2007
3 Points on Line	Univariate Least Median-of-Squares Estimator	2006
Conjunctive Normal Form SAT	k-OV	2005
Conjunctive Normal Form SAT	OV	2005
Geometric Base	All Distant Horizon Edges	2005
3SUM'	Static Dihedral Rotation Queries	2003
Combinatorial BMM	CFG Parsing	2002
Geometric Base	Smallest Color-Spanning Strip	2001
3SUM'	Equal Distance	2001
3SUM'	Segments Containing Points	2001
Segments Containing Points	Polygon Containment under Translation	2001
Segments Containing Points	Convex Polygon Containment under Rotation	2001
Segments Containing Points	Convex Polygon Containment under Rotation and Translation	2001
Segments Containing Points	1-Sided Segment Hausdorff Distance under Translation	2001
Segments Containing Points	Segment Hausdorff Distance under Translation	2001
Point on 3 Lines	Minimum-Area Star-Shaped Hull, Restricted	1998
Strips Cover Box	1-Fillability Problem	1998
2D Maximum Subarray	Distance Product	1998
2D Maximum Subarray	Distance Product	1998
Geometric Base	Perfect 2D Binary Space Partitioning	1997
3SUM	3SUM'	1995
3SUM'	3SUM	1995
3SUM'	Geometric Base	1995
Geometric Base	3SUM'	1995
3SUM	3 Points on Line	1995
3 Points on Line	Point on 3 Lines	1995
Point on 3 Lines	3 Points on Line	1995
Geometric Base	Separator1	1995
Geometric Base	Separator2	1995
Geometric Base	Strips Cover Box	1995
Strips Cover Box	Triangles Cover Triangle	1995
Triangles Cover Triangle	Hole in Union	1995
Hole in Union	Triangles Cover Triangle	1995
Triangles Cover Triangle	Triangle Measure	1995
Strips Cover Box	Point Covering	1995
Geometric Base	Visibility Between Segments	1995
Geometric Base	Visibility From Infinity	1995
Triangles Cover Triangle	Visible Triangle	1995
Visible Triangle	Triangles Cover Triangle	1995
Geometric Base	Planar Motion Planning	1995
Triangles Cover Triangle	3D Motion Planning	1995
CFG Parsing	Combinatorial BMM	1975
Directed, Weighted APSP	Distance Product	1974
Distance Product	Directed, Weighted APSP	1974
Max-Weight 4-Clique	Max-Weight k-Clique
Negative Triangle Detection	Negative Triangle Search
Negative Triangle Search	Negative Triangle Listing
Negative Triangle Detection	Minimum Witness Finding
Minimum Witness Finding	All Pairs Minimum Witness (APMW)
Triangle Detection	Triangle in Unweighted Graph
OV	k-OV
OV	Most OV
OV	Unbalanced OV
k-Clique	Max-Weight k-Clique
k-Clique	Min-Weight k-Clique
Conjunctive Normal Form SAT	MaxSAT
Triangle Detection	Negative Triangle Detection
Triangle Detection	Exact Triangle
Triangle Detection	Triangle Listing
Real 3SUM	All-Reals 3SUM
Real Exact Triangle	Real All-Edges Exact Triangle
Real All-Edges Exact Triangle	#Real All-Edges Exact Triangle
Triangle Collection	All-Color-Pairs Triangle Collection
Triangle Collection*	All-Color-Pairs Triangle Collection*