Chao Xu
  • Member for 9 years, 10 months
  • Last seen more than a month ago
Sorting when there are only O(log n) many different numbers
Accepted answer
14 votes

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$ ...

View answer
Circles covering a rectangular, how to verify it?
Accepted answer
9 votes

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 ...

View answer
Wiring Length Minimization
Accepted answer
7 votes

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 ...

View answer
The equivalence relations cover problem (in graph theory)
6 votes

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 ...

View answer
Convex polygon formulation
Accepted answer
6 votes

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 ...

View answer
Efficient algorithm for this optimization problem? Dynamic programming?
Accepted answer
5 votes

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
Determining the minimum number of edges to add in order to be 3-connected
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
Complexity of the Kitten Adoption problem
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
Upper bound on the number of edges relative to the height of a DFS tree
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 $...

View answer
Efficiently checking if two star graphs are disjoint
3 votes

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 ...

View answer
Efficient algorithms for identifying the diamond fork&join vertices and the diamond pairs in directed acyclic graph?
Accepted answer
2 votes

$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
Enumerate all pairs, in order of increasing distance, efficiently
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
The heaviest induced subgraph problem
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
Find interval sums with minimum number of operation
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
Search for minimum in an array of $k$ monotonic subarrays
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
Finding the size of the smallest subset with GCD = 1
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
Hates Pepole Nice Algorithm
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)$.

View answer