15
The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width.
Fix any constant $\epsilon>0$ and consider the Independent Set problem restricted to graphs of tree width at most $n \log_2(1+\epsilon) = \Theta(\epsilon n)$, where $n$ is the number of vertices. Call this problem $\Pi_\epsilon$.
Lemma ...
4
Here is a natural problem from graph theory where the proof and the algorithm are closely intertwined. In my view, one can discover this algorithm only via thinking about the proof and the algorithm "in parallel." The task is this:
Input: An undirected graph.
Task: Find a subgraph with maximum edge-connectivity.
Note: What makes the task non-trivial is ...
3
We can create such problem by padding assuming ETH. Take an np-complete problem L such that L is decidable in time $O(2^n)$, by padding L with some dummies 1 create $L' = \{1^{n-(log_21.01)n} x:|x|=(log_21.01)n \land x \in L\}$ it is easy to prove that $L'$ is complete for np and the running time of $L'$ is exactly $O(1.01^n)$.
3
Here's an argument that you need time quadratic in the number of polygons. More precisely,
you should not be able to find containing pairs among $n$ $k$-sided polygons in time $O(n^{2-\epsilon})$, for any $k=O(n^{\delta})$ and any $\epsilon,\delta>0$ It's a reduction from the orthogonal vectors problem, the problem of finding two disjoint binary vectors ...
2
I see several advantages of mastering the proof of correctness and complexity of an algorithm. I list them below and illustrate with a concrete example. I tried to stay in the domain of classical textbook algorithms.
Understanding why the algorithm works
Certainly the most obvious reason of having proofs. Many algorithms exploit some structure in the ...
2
A practical answer: In my career I encountered a few scenarios, some with my direct involvement, where I had to prove that my algorithm performs just as good as the currently best known possible. There are many examples where such knowledge can have a direct effect on one's career... In my experience, making a good claim at a design review meeting or to your ...
Only top voted, non community-wiki answers of a minimum length are eligible
