# Algorithms and computational complexity of clique and biclique covers

I've been reading a paper by a mathematical chemist. He proposes some indices to measure the complexity of molecules. From here on in, instead of molecules, think undirected connected graphs: a vertex is an atom, and an edge is a bond between atoms. It's possible to consider colorings of the vertices, to tell the Nitrogens apart from the Carbons, say, but I'll ignore that part for now.

The point: the indices he suggests are motivated by heuristics and experimental "looks good so far"-ness. I think there must be some actual theory known about some of these quantities, and I'm hoping to get some pointers here.

Fix a graph $G$. Let $C$ and $C'$ be two covers of $G$. Say $C$ and $C'$ are the same kind of cover if they contain the same types of subgraphs in equal numbers. (Note $C$ and $C'$ do not have to be isomorphic.) Now we define the following quantities:

$k_S(G) =$ number of kinds of minimal edge clique covers of $G$
$k_T(G) =$ total number of minimal edge clique covers of $G$
$k^{bi}_S(G) =$ same as $k_S(G)$ but for bicliques
$k^{bi}_T(G) =$ same as $k_T(G)$ but for bicliques
$p_S(G) =$ number of kinds of partitions of the edges of $G$ into cliques
$p_T(G) =$ total number of partitions of the edges of the graph into cliques
$p^{bi}_S(G), p^{bi}_T(G)$ as above, but with partitions of $G$ into bicliques

Empirically, it is apparently easier to calculate the $p$ measures than it is to calculate the $k$ measures. I expect something must be known somewhere about calculating some of these quantities. Can anyone provide algorithms, computational hardness, etc.? Thanks.

• Are these graphs from a restricted class? I mean do you want algorithms for these measures on arbitrary graphs or just those arising in chemistry? If you are not looking for general algorithms then stating the properties of the graphs arising in chemistry can be helpful in finding an answer to your question. Oct 15, 2010 at 18:21
• “Empirically, it is apparently easier to calculate the p measures than it is to calculate the k measures.” I assume that “easier” means that the computation is faster (rather than, say, that the algorithm is easy to describe). If this is the case, which kind of algorithms are you talking about? If you are enumerating all the possibilities by backtracking or by some other method, the p measures are less than the corresponding k measures, which means that it may not be surprising that the p measures are faster to compute. Oct 19, 2010 at 2:42