Bicolored independent sets and bicliques.
Jean-Fraņcois Couturier, Dieter Kratsch · Cologne Twente Workshop on Graphs and Combinatorial Optimization · 2011
We introduce the decision problem Bicolored Independent Set which generalizes the well-known NP-complete graph problem Independent Set. We present an O(1.2691^n) 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(1.2691^n) time algorithm solving #Bipartite Biclique and an O(1.6107^n) time algorithm solving #Non-induced Biclique.