Skip to content
# Poly-time Reduction

semi-induced dimatching in undirected graphs
Equidistances
(Cook-)Karp completeness of a variant of vertex cover
Karp hardness of searching for a matching split
Resolving a conjecture: (Weakly) Almost-Clique is also difficult
Crossword
Packing triangles, this time their vertices are colored
Graph orientation in which there is at most one walk between any pair of vertices
Longest cycle contained in two cycles
Graph orientation satisfying that all nodes in a given subset have in- or out-degree 0, and every other node positive indegree
Convex Polygon Cover is hard
Hard to select points in a plane
Karp hardness of a guarding set in digraph
A special case of longest path problem
Maximum matching respecting ordering constraints
Ordering the incident edges of each vertex to have a specified pre-order traversal
Clique with given number of outer-incident edges
Vertex cover with covering radius 2
Embedding trees of diameter four is NP-hard
DOMINATING SET≤p MINESWEEPER
NP tells the tale: a simply equidistant set
NP-completeness of Bipartite Exact Cut
NP tells the tale: a diameter-decreasing planted clique
NP tells the tale: An equidistant set
NP tells the tale: Vašek Chvátal is a hero
Matching Erosion
Missing edges covered by two nodes
“Regular” Spanning Tree
Saturating all debts using few transactions
Multi-way cut
Modular square roots of -1
Vertex cover that covers all the triangles
Hard to partition into triangles
Prasolov mathematics still has much to do these days
Exact Weight Perfect Matching of Bipartite Graphs

polynomial, time, reduction