Encompassing Computer Science Workshop 2015

Complexity of generating

Not scheduled

1m

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 $Axgeqb$, $0leqxleqc$ 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^{\prime }subseteqI=1,...,n$ such that the corresponding graph is connected on $V$ is tractable. In contrast, generating all such subsets connecting two given vertices $v^{\prime },v^{″}inV$ 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^{logn}$ time can be reduced to Boolean dualization, which, in its turn, is also solvable in quasi-polynomial time.