Bicolored independent sets and bicliques

We introduce the decision problem Bicolored Independent Set which generalizes the well-known NP-complete graph problem Independent Set. We present an O(n1.2691)O(1.2691n) time algorithm solving its counting analogue #Bicolored Independent Set. We show how to use this algorithm to establish algorithms solving biclique counting problems and provide an O(n1.2691)O(1.2691n) time algorithm solving #Bipartite Biclique and an O(n1.6107)O(1.6107n) time algorithm solving #Non-induced Biclique.

► NP-complete graph problems.
► Exact exponential time algorithms.
► Existence and counting problems.
► Bicolored independent sets.
► Bipartite bicliques and non-induced bicliques.