Intersection representations of matrices by subtrees and unicycles on graphs

Consider a 0–10–1 matrix M(i,j)M(i,j) with columns C={c1,c2,…,cm}C={c1,c2,…,cm}, and rows R  , or—equivalently—a hypergraph M(R,C)M(R,C) having M as its adjacency matrix (where R are the vertices and C   are the hyperedges). Denote ri={cj|cj∈Cri={cj|cj∈C and M(i,j)=1}M(i,j)=1}. We consider the following two problems: (a) Is there a graph H, with vertex set C  , such that every vertex subgraph H(ri)H(ri) of H is a tree and the intersection of every two such trees is also a tree? (b) Is there a graph H, with vertex set C  , such that every H(ri)H(ri) is a unicycle and the intersection of every two and every three unicycles is a tree? These questions occur in application areas such as database management systems and computational biology; e.g., in the latter they arise in the context of the analysis of biological networks, primarily for the purpose of data clustering. We describe algorithms to find such intersection representations of a matrix M (and equivalently of the hypergraph M), when they exist.