acyclic decomposition of hypergraphs

90 Views Asked by At

The following is from the paper Arboricity: An acyclic hypergraph decomposition problem motivated by database theory by Yeow Meng Chee, Lijun Ji, Andrew Lim, Anthony K.H. Tung:

enter image description here

enter image description here

Question: For an arbitrary finite hypergraph $\mathcal{H}$, does $\mathcal{H}$ always have a finite acyclic decomposition? Are there any references?

1

There are 1 best solutions below

0
On BEST ANSWER

For an arbitrary finite hypergraph $\mathcal{H}$ put each edge in a separate component, that is, take $\mathcal{A}_i = \{A_i\}$. All such one-hyperedge graphs have all degrees equal to one, so they are acyclic.

I hope this helps $\ddot\smile$