New answers tagged approximation-hardness
1
For all $k\geq 3$, the problem maximum induced matching is APX-hard for $k$-regular bipartite graphs. See this paper.
A matching $M$ of a graph $G$ is induced if for every pair of edges $e,e'$ in M, there is no edge between them in $G$.
3
The problem of finding the shortest simple cycle through two vertices in a weighted undirected graph can be solved in the same time as Dijkstra's algorithm for a single shortest path, by applying Suurballe's algorithm for finding disjoint $s$–$t$ shortest paths in a directed graph.
It doesn't quite work to turn your given undirected graph directed by ...
Top 50 recent answers are included
