P504: Enumerate all maximal induced bipartite subgraphs in a graph

P504: Enumerate all maximal induced bipartite subgraphs in a graph

Input:

A graph $G = (V, E)$.

Output:

All maximal induced bipartite subgraphs in $G$.

Complexity:

$O(|V|(|E| +|V| \alpha(|V|)))$ delay, where $\alpha(\cdot)$ is the inverse of Ackerman function.

Comment:

Exponential space. Proximity search. A solution may be disconnected.

Reference:

[Conte2019] (Bibtex)