The matroid structure of representative triple sets and triple-closure computation

DOI10.1016/J.EJC.2018.02.013zbMATH Open1384.05066arXiv1707.01667OpenAlexW2726984384MaRDI QIDQ1746594FDOQ1746594

Authors: Carsten R. Seemann, Marc Hellmuth

Publication date: 25 April 2018

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The closure

e x t r m c l (R)

of a consistent set

R

of triples (rooted binary trees on three leaves) provides essential information about tree-like relations that are shown by any supertree that displays all triples in

R

. In this contribution, we are concerned with representative triple sets, that is, subsets

R^{'}

of

R

with

e x t r m c l (R^{'}) = e x t r m c l (R)

. In this case,

R^{'}

still contains all information on the tree structure implied by

R

, although

R^{'}

might be significantly smaller. We show that representative triple sets that are minimal w.r.t. inclusion form the basis of a matroid. This in turn implies that minimal representative triple sets also have minimum cardinality. In particular, the matroid structure can be used to show that minimum representative triple sets can be computed in polynomial time with a simple greedy approach. For a given triple set

R

that "identifies" a tree, we provide an exact value for the cardinality of its minimum representative triple sets. In addition, we utilize the latter results to provide a novel and efficient method to compute the closure