Hard-looking algorithmic problems made easy by theorems

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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)

Answer 5

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

Problem: Design an $O(n)$ representation of planar graphs 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 it to a list as a key and its neighbors as values. The remaining graph is also planar and has a vertex with degree at most 5. So the space consumed is at most $5n$. We can check if $u$ is in the adjacency list of $v$; if not we can check if $v$ is in the adjacency list of $u$. This takes at most $10$ steps.

Answer 6

I think the posterchild for this category, at least as far as difficulty assymetry is concerned, is the following problem:

Given a planar graph $G$, is $G$ 4-colourable?

The Four colour theorem simplifies the algorithm to return true.

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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

Answer 11

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$

More about this can be read on The decisional diffie-hellman problem, Boneh'98 or a google lookup on Pairings

Answer 12

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

Answer 13

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.

Answer 14

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.

Answer 15

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.

Answer 16

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.