8
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Oct 15, 2010 at 18:21
  • $\begingroup$ “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. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 19, 2010 at 2:42

1 Answer 1

Reset to default
5
$\begingroup$

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

Parameterized complexity of the clique partition problem

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Aaron Sterling
    Commented Oct 18, 2010 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.