I'm trying to understand the following problem if anyone can help I'll be very grateful

Instance: undirected, unweighted, connected graph graph $G=(V,E)$.

Question: find a minimum cycle basis $B = \{C_1,\dots,C_\nu\}$ of $G$ (where $\nu = |E|-|V|+1$ is the cyclomatic number) respect to non-empty pairwise cycle intersections. More precisely let $B$ minimize:

$$\sum_{C_i, C_j \in B} \cap(C_i, C_j), i \neq j$$

Where $\cap(C_i, C_j)$ is defined as follows

$$\cap(C_i, C_j) := \begin{cases} 1 & C_i \cap C_j \neq \varnothing \\ 0 & C_i \cap C_j = \varnothing \\ \end{cases} $$

And the intersections considered are: edge intersections.

There is a longstanding theory that describes the problem of minimizing cycle lengths (or weights) instead of cycle intersections. The following survey gives a complete picture:

Cycle bases in graphs characterization, algorithms, complexity, and applications Kavitha T., Liebchen C., Mehlhorn K., Michail D., Rizzi R., Ueckerdt T., Zweig K.A. (2009) Computer Science Review, 3 (4) , pp. 199-243.

I couldn't find a similar treatment of the problem of minimizing intersections. Any comment, suggestion or bibliographic reference will be of great help.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.