Description
I will briefly survey joint results with Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Kazuhisa Makino on the complexity of generation (also called enumeration) problems.
Several examples:
1. Generating all negative cycles of a graph is intractable.
Furthermore, it can be reduced from enumerating all vertices of a polyhedron given by linear inequalities. Thus, the latter problem is intractable too. Yet, in case of the bounded polyhedra the question remains open (so-called polytope-polyhedron problem).
2. Generating all maximal frequent sets in binary matrices is intractable, in contrast to generating all minimal infrequent sets, which is tractable.
3. Generating all minimal integer vectors $x$ satisfying $Ax geq b$, $0 leq x leq c$ is tractable whenever $A$ is a non-negative integer matrix. Note that without this restriction we obtain just Integer Programming and already verifying feasibility becomes NP-hard. Also generating all maximal infeasible integer vectors for the above system is not tractable.
4. Generating all minimal strongly connected arc subgraphs of a (strongly connected) digraph is tractable. In contrast, generating all maximal NOT strongly connected ones (or, in other words, all minimal directed cuts) is intractable.
5. Given a graph $G = (V,E)$ and an edge-cover $E = E_1 cup ... cup E_n$.
Generating all inclusion-minimal subsets $I' subseteq I = {1,...,n}$ such that the corresponding graph is connected on $V$ is tractable. In contrast, generating all such subsets connecting two given vertices $v', v'' in V$ is intractable; as well as generating all "maximal not connecting subsets" in both cases.
Many of the above cases are tractable, because they belong to an important class of the so-called dual-bounded problems. Such problems, in quasi-polynomial $n^{log n}$ time can be reduced to Boolean dualization, which, in its turn, is also solvable in quasi-polynomial time.
Primary author
Dr
Vladimir Gurvich
(Rutgers University)
