Because you asked for minimum number of comparisons, so I assume the algorithm can only compare the numbers. The idea is to extend the sorting lower bound argument. Assume you want to sort $n$ ...

Create a Voronoi diagram on the $n$ disk centers in $O(n\log n)$ time. Intersect it with the rectangle in $O(n)$ time. Now you have a set of convex shapes, thus the furthest point away from the ...

This problem is NP-hard. Assume every vertex is a splitter that can split to any number of degrees, then your problem is precisely the Steiner tree problem on a graph, where the set of source and ...

Although I don't know the name for such problem, I can show this problem is NP-hard. For a triangle free graph, all equivalence classes must be a matching. The minimum number of equivalence classes ...

Theorem 1. For every polygon with edge length sequence $a_1,\ldots,a_m$, there exist a convex polygon with same edge length sequence. Proof. Here. Definition. $a_1,\ldots,a_n$ be $n$ non-negative ...

This is just an extension to @Sébastien Loisel's answer. Notice minimize $(x_i-y_i)^2$ subject to $x_i-x_{i-1}\ge c_i$ is equivalent to minimize $(x_i-(y_i-c_i))^2$ subject to $x_i\geq x_{i-1}$. Let $... View answer Accepted answer 5 votes For this special case of$3$-connectivity, it has been solved by Watanabe and Nakamura. The algorithm runs in$O(n(n+m)^2)$time, where$n$and$m$are the number of vertices and edges of the input ... View answer Accepted answer 5 votes This is the min-cost max-flow problem. Consider a graph$G=(A\cup B\cup \{s,t\},E)$, where$A$is the set of kittens,$B$is the set of people. Let$C:E\to \mathbb{R}^+$be the capacity of the ... View answer Accepted answer 4 votes After running a DFS, all the edges in$G$can be classified as tree edges or back edges. Each back edge connects a vertex on the tree to one of it's ancestors. For each vertex it can point to at most$...

I assume the graph $G$ is fixed, and you are doing $M$ queries on $G$. Your algorithm takes $O(Mn\log n+t)$ time, where $t$ is the amount of time to build the adjacency list. We can use the same ...
$G=(V,E)$ is the graph we work on. Problem 2: $\Diamond_F(reverse(G))=\Diamond_J(G)$, where $reverse(G)$ reverses all the edges of G. Problem 3: This can be solved in $O(nm)$ time. For each vertex $... View answer 2 votes Consider all the point on the x-axis, then you are describing sorting$X-X$. A special case of$X+Y$sorting(one can actually show they are equivalent in terms of running time). This is not known to ... View answer 1 votes$\newcommand{\R}{\mathbb{R}}$Let's consider a special case of the problem where vertex has negative weight and edges have positive weight. So$w_v: V\to \R^-$and$w_e: E\to \R^+$. Finding the ... View answer 1 votes This problem was solved recently. The naive greedy algorithm works. David Basin, Felix Klaedtke, Eugen Zălinescu, Greedily computing associative aggregations on sliding windows, Information ... View answer 1 votes For$k>2$, the best algorithm takes$\Omega(n)$time. Consider when$A[i] = i$for all$i$except$i=j$, and$A[j]=-1$. In this situation, you can't find the minimum without examining every ... View answer 1 votes This problem is equivalent to the following, and it's trivial to construct reduction both ways. Given a list of bit vectors, find the minimum number of them such that and all of them result the$0$... View answer Accepted answer 0 votes This is equivalent to check if the "hate" graph is bipartite. Which can be done in linear time with respect to number of edges. Thus$O(n^2)\$.