New answers tagged

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