3
$\begingroup$

I'm trying to decompose an arbitrary undirected graph G into minimal subgraphs so that no cycle of the original graph does cross the boundaries of a subgraph. The subgraphs are defined by a partition of edges of G, meaning that each edge is assigned to exactly one subgraph while each nodes is present in all subgraphs that contain at least one edge connected to that node.

Stated another way, two edges are part of the same subgraph if, and only if there is some cycle in G containing both edges.

For example, given the following graph, the blue circles show how eges are grouped into subgraphs:

As a result, decomposing the graph above would yield the following 9 subgraphs:

I've tried to come up with an algorithm by first computing the bridges and articulation points of the graph and then using this information to compute where boundaries between subgraphs lie or something, but without success. Below is the same graph with its bridges and articulation points highlighted in orange:

Is there an efficient algorithm to compute the partition I've described above?

Some background

I'm implementing an algorithm to propagate properties, and changes to those properties, according to some specific rules through a big (e.g. > 106 nodes), static, undirected graph. The algorithm scales with the number of property changes for trees but scales with the number of nodes of the graph if the graph contains cycles.

The graphs I'm working with may contain arbitrary cycles but most of them will be very small (e.g. < 5 nodes) and often not connected to other cycles.

My approach is to use different algorithms for part of the graph that contain cycles and the parts that don't. This works if I can transform the given graph into a tree where each node of the tree either represent a single node of the given graph or a subgraph containing cycles of the given graph.

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't see how you can decompose a 2-connected graph into such components. $\endgroup$
    – Dima Pasechnik
    Commented Jul 10, 2021 at 16:26
  • $\begingroup$ @DimaPasechnik It can't. A 2-connected graph will be decomposed into a single component. $\endgroup$
    – Feuermurmel
    Commented Jul 10, 2021 at 21:01
  • $\begingroup$ then you are solving a classical problem, see the answer below $\endgroup$
    – Dima Pasechnik
    Commented Jul 11, 2021 at 6:07

1 Answer 1

Reset to default
2
$\begingroup$

The partition you are describing is given by the block-cut tree of $G$. It can be computed in linear-time by a classic algorithm of Hopcroft and Tarjan based on depth-first search (see the linked wikipedia page for a description of the algorithm).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes! This matches exactly what I had in mind! I was already able to implement the algorithm and it seems to work. :) $\endgroup$
    – Feuermurmel
    Commented Jul 11, 2021 at 7:58
  • $\begingroup$ I used the function bicon() from this excerpt as a reference. If anyone knows which book this is, that would be great to know! $\endgroup$
    – Feuermurmel
    Commented Jul 11, 2021 at 7:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .