1
$\begingroup$

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.

$\endgroup$

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.