Finding Matrimonial Circuits in some Amerindian Kinship Networks: An Experimental Study

We consider the problem of deciding the existence of matrimonial circuits, and finding implexa in kinship networks. These networks can be modeled by acyclic digraphs. A matrimonial circuit can be seen as vertex-disjoint directed paths from special starting to special ending vertices of these acyclic digraphs. An implex is the set of all matrimonial circuits of a given pair of special vertices. We present methods based on Eppstein´s reduction and algorithms for finding junctions to decide the existence of matrimonial circuits. The efficiency of these methods is shown in our empirical results on seven Amerindian kinship networks. To enumerate all implexa, we present an algorithm, given that the kinship network is limited. We present some descriptive statistics which help us to justify the good performance of the methods. We incorporate to our software tool, the Kinship Machine, a feature to enumerate matrimonial circuits. This tool is being used by Anthropologists to analyze Amerindian kinship networks of northern Brazil.