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.