<p>I am not sure if this is what you need.</p>

<p>Both Edge Clique cover and Edge Clique partition are in FPT, see</p>

<p><a href="http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf">Data reduction and exact algorithms for clique cover</a></p>

<p><a href="http://crpit.com/confpapers/CRPITV77Mujuni.pdf">Parameterized complexity of the clique partition problem</a></p>

<p>Biclique cover is also studied and shown to be in FPT.</p>

CC BY-SA 2.5
2010-10-18T19:24:39.703Z
Thanks very much for bringing this question back from the dead. I don't know if it's what I need either, but I'll take a look at the references you linked to soon.  I appreciate it.
Aaron Sterling
CC BY-SA 2.5
2010-10-15T17:19:22.917Z
2010-10-15T17:19:22.917Z
yzll
<p>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.</p>

<p>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.</p>

<p>Fix a graph $G$.  Let $C$ and $C'$ be two covers of $G$.  Say $C$ and $C'$ are the <i>same kind</i> 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:</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-10-15T18:21:45.153Z
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.
Kaveh
CC BY-SA 2.5
2010-10-19T02:42:05.697Z
“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.
Tsuyoshi Ito
<cc.complexity-theory><ds.algorithms><graph-algorithms><clique>
Algorithms and computational complexity of clique and biclique covers
Aaron Sterling
# Algorithms and computational complexity of clique and biclique covers

(Asked by: username_0 on 2010-09-18)

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.

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, clique

> **Comments:**
> **username_1**: 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.  
> **username_2**: “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.  

---

## 1 answers

### Answer by username_3 on 2010-10-15. Score: 5 | Accepted answer

I am not sure if this is what you need.

Both Edge Clique cover and Edge Clique partition are in FPT, see

[Data reduction and exact algorithms for clique cover](http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf)

[Parameterized complexity of the clique partition problem](http://crpit.com/confpapers/CRPITV77Mujuni.pdf)

Biclique cover is also studied and shown to be in FPT.

> **Comments:**
> **username_0**: Thanks very much for bringing this question back from the dead. I don't know if it's what I need either, but I'll take a look at the references you linked to soon.  I appreciate it.  

---

