# Hard-looking algorithmic problems made easy by theorems

I am looking for nice examples, where the following phenomenon occurs: (1) An algorithmic problem looks hard, if you want to solve it working from the definitions and using standard results only. (2) On the other hand, it becomes easy, if you know some (not so standard) theorems.

The goal of this is to illustrate for students that learning more theorems can be useful, even for those who are outside of the theory field (such as software engineers, computer engineers etc). Here is an example:

Question: Given integers $n, k, l, d$, does there exist an $n$-vertex graph (and if so, find one), such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$?

Note that we require that the parameters are exactly equal to the given numbers, they are not just bounds. If you want to solve this from scratch, it might appear rather hard. On the other hand, if you are familiar with the following theorem (see Extremal Graph Theory by B. Bollobas), the situation becomes quite different.

Theorem: Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree $d$, if and only if one of the following conditions is satisfied:

• $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$,
• $1\leq 2d+2-n\leq k\leq l = d< n-1$
• $k=l=d=n-1.$

These conditions are very easy to check, being simple inequalities among the input parameters, so the existence question can be answered effortlessly. Furthermore, the proof of the theorem is constructive, resolving the construction issue, as well. On the other hand, this result does not appear standard enough, so that you can expect everybody to know about it.

Can you provide further examples in this spirit, where knowing a (not so standard) theorem greatly simplifies a task?

-
I am not sure I fully understand your questions. The example you give is a non-trivial problem for which Bollobas has given an algorithm (which implies a characterization). So my impression with your example is that any non-trivial algorithm will be an answer... –  Bruno Feb 13 '14 at 7:27
Primality and the AKS theorem. –  Lamine Feb 13 '14 at 10:32
@Bruno: What I mean is that the algorithmic task becomes much easier if you know a theorem, which is not well known, so one may have never heard of it. The presented example is not perfect in the sense that here the theorem does not just help, it actually solves the problem. What I am really looking for is when a theorem helps, provides some useful shortcut, but does not fully solve the problem in itself. –  Andras Farago Feb 13 '14 at 13:48
Community wiki? –  Joshua Grochow Feb 13 '14 at 22:53
Robertson–Seymour theorem, also conjectures that make deterministically finding primes easy. –  Kaveh Feb 14 '14 at 22:35

Deciding isomorphism of simple groups, given by their multiplication tables. The fact that this can be done in polynomial time follows directly from the fact that all finite simple groups can be generated by at most 2 elements, and currently the only known proof of that fact uses the Classification of Finite Simple Groups (perhaps the largest theorem - in terms of authors, papers, and pages - ever proven).

-
This is a great example! BTW the comments to this answer claim that in some sense this theorem is about as hard as the classification: mathoverflow.net/a/59216/35733 –  Sasho Nikolov Feb 13 '14 at 19:22

If I understand your question correctly, a canonical example would be deciding if a graph $G$ has an Eulerian circuit: equivalent to checking that $G$ is connected and every vertex has even degree.

-

This afternoon I was reading Stringology -- the "Real" string theory.

Problem: If $x$ and $y$ are two strings over some alphabet when are there some positive integers $m, n$ such that $x^m = y^n$.

Theorem: There are positive integers $m,n$ such that $x^m = y^n$ if and only if $xy = yx$.

-

Whether a real (multivariate) polynomial $p$ can be expressed as a sum of squares of real polynomials can be solved by reduction to semi-definite programming. Need to know SDP and that SDP can be solved efficiently.

-

Another example: given an undirected graph, does it have a minimum cut in which all the edges are disjoint? If so, find one.

At first sight this might appear hard. It becomes easy, however, if you know the result that an undirected $n$-vertex graph can have at most $n(n-1)/2$ minimum cuts, and they can all be listed in polynomial time.

It can be extended to nearly-minimum cuts, which are larger than the minimum cut, but at most by a constant factor. Their number is still bounded by a polynomial.

(I did not search for a reference, my recollection is that these results are due to D. Karger.)

-

Finding the number of (distinct) real roots of a real polynomial, either in all of ℝ or in a given interval. Sturm's theorem tells you that a sequence of polynomials that fulfils a small number of requirements can be used to count the number of real roots of a polynomial with real coefficients.

Then, all you have to do is construct such a sequence (which isn't very difficult, but requires some edge cases and handling of the case of non-separable polynomials), and Bob's your uncle.

Surprisingly, few people know about this result, despite it being quite old (1829). It is used in many Computer Algebra Systems, but all the mathematics professors at my university whom I asked either didn't know Sturm's Theorem at all or they only knew it by name and that it has something to do with roots of polynomials.

Most people are quite surprised when you tell them that something like counting real roots exactly is this easy and does not require any approximation, considering that finding roots is much more difficult. (Remember that for polynomials of degree ≥ 5, there does not even exist a “proper” formula for roots)

-

Problem: Satifsiability of an MSO (monadic second-order logic) formula over finite words.

Theorem: MSO is equivalent to finite automata over finite words.

The above can be lifted to infinite words, finite trees, infinite trees.

-

Decisional Diffie Hellman

It states: given $(g, g^a, g^b, g^c)$ where $g$ is some generator of a cyclic group $\mathbb{G}$, verify if $g^c = g^{ab}$

Under the standard assumptions of hardness of discrete log problem, this problem may also seem hard.

However, with bilinear maps this problem is easy and can be verified as $$e(g,g^c) \stackrel{?}{=} e(g^a,g^b)$$

where $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$

-

A slightly more complicated example: nonnegative matrix factorization, when the nonnegative rank is constant.

Say I give you a matrix $A \in M_{m \times n}$ along with the promise that there exist nonnegative $U \in M_{m \times k}$, $V \in M_{k \times n}$ such that $A = UV$. The problem is to find such a factorization for $A$.

With a few lines of elementary linear algebra you can reduce the problem to solving a system of polynomial inequalities in $O(r^2)$ variables, where $r$ is the nonnegative rank of the matrix you want to factor.

Using Renegar's algorithm as a hammer, you can then solve this in time $(mn)^{O(r^2)}$ and hence recover $U$ and $V$. This is not far from optimality, since it's ETH-hard to solve NMF in time $(mn)^{o(r)}$.

-

(Trivially) the existence of a Nash Equilibrium in a finite game, an even number of Hamiltonian Paths in a cubic graph, various types of fixed points, decently balanced comparisons in partial orders, and many other PPAD problems.

-
The existence of Nash Equilibrium - and many of the other proofs of existence that characterized PPAD - don't seem to make any of these problems any easier to solve algorithmically... –  Joshua Grochow Mar 2 '14 at 16:49
I was referring to the decision version of these problems. –  Yonatan N Mar 2 '14 at 22:20

Theorem: Every planer graph has a vertex with degree at most 5.

Problem: Design $O(n)$ representation of planer graph where we can check if $(u, v)$ is an edge in $O(1)$ time.

We can remove the vertex with degree at most 5 and add to a list as a key and its neighbors as values. Remaining graph is also planer and has a vertex with degree at most 5. So space consumed is at most $5n$. We can check if $u$ is in adjacency list of $v$ if not we can check if $v$ is in adjacency list of $u$. This takes at most $10$ steps.

-

less complex examples: there are some theorem-like properties that show that greedy algorithms for some problems are optimal. its not so obvious to the uninitiated a minimum spanning tree can be found by a greedy algorithm. somewhat similar conceptually is Dijkstra's algorithm to find a shortest path in a graph. actually in both cases the associated "theorems" are nearly the same as the algorithms.

-
I think this will be a better answer if for example you include a statement of the cut property of MST and mention how it implies the correctness of a whole class of greedy MST algorithms. –  Sasho Nikolov Feb 14 '14 at 3:37
MST cut property listed on the wikipedia pg. maybe you can ref other generalizations not covered there. btw recall the questioner asked for examples serving "those outside the theory field" (other nice examples given may be too advanced for outsiders) –  vzn Feb 14 '14 at 3:39
that cut property does not imply the correctness of the greedy algorithms as far as I can see. The property I mean is: a spanning tree $T$ is an MST if the following holds; for every edge $e$, $T - e$ has two connected components - let their vertices be $A$ an $B$; then $e$ is a minimum weight edge on the cut $E(A,B)$. –  Sasho Nikolov Feb 14 '14 at 3:48

Find the sequence of Fibonacci numbers that are the product of other Fibonacci numbers. For example, the Fibonacci number 8 is in the sequence because 8=2*2*2, and 2 is a Fibonacci number that is not equal to 8. The Fibonacci number 144 is in the sequence because 144=3*3*2*2*2*2, and both 2 and 3 are Fibonacci numbers that are not equal to 144.

Carmichael's theorem implies that 8 and 144 are the only terms of this sequence.

-

Finding min-cuts. Given a weighted graph and two vertices $((V, E), s, t)$, find $E' \subset E$ such that $s$ and $t$ are not connected in $(V, E')$, such that the total weight of $E'$ is maximised.

By the max-flow/min-cut theorem, this reduces to finding the maximum flow from $s$ to $t$ in $(V, E)$. This problem is not trivial, but a pretty simple idea works: if we can increase the flow along some $s$-$t$ path, do so. The tricky part is choosing which paths to augment in a way which finds the max-flow quickly.

-
One can say that flow is easy if you know that LP is easy. Thus two big theorems (LP in poly time and maxflow-mincut) allows us to compute min-cuts. –  Chandra Chekuri Feb 17 '14 at 21:41
@ChandraChekuri, my personal feeling is that that doesn't quite fit the question: the theorem that LP is solvable in polytime doesn't help us to actually constructed an algorithm for min-cuts. We need the actual LP algorithm. –  Max Feb 18 '14 at 11:13
Not really. If you can find the min-cut value in a given graph efficiently then you can use such an algorithm to find the actual cut itself. –  Chandra Chekuri Feb 20 '14 at 15:31

Here is another example: given an undirected simple graph, decide if it has two vertex-disjoint circuits.

One can naturally try to construct a recursive algorithm, by reducing the graph to a smaller one. This can be carried out easily, as long as the graph has a vertex with degree $\leq 2$. If, however, a graph is reached with minimum degree $\geq 3$, then it seems hard to find out how to continue, unless you know the following theorem (which originates in two papers, published independently by L. Lovasz and G. Dirac in 1965):

Theorem. If a simple graph with minimum degree $\geq 3$ does not have two vertex-disjoint circuits, then the graph can only be one of the following three types: (1) $K_5$, (2) a wheel graph, (3) $K_{3,n-3}$, with possibly any edges added to the the 3-vertex class.

Since it is easy to check whether a graph is one of the graphs allowed by the Theorem, this provides us with a polynomial-time algorithm for the decision problem.

Notes: (1) The proof of the theorem is not at all easy. (2) Once we decided that two disjoint circuits exist, it seems less clear how to solve the associated search problem, that is, how to actually find such circuits. The theorem does not give direct advice to that.

-