Algorithms for Junctions in Directed Acyclic Graphs

Abstract

Given a pair of distinct vertices u, v in a graph G, we say that s is a junction of u, v if there are in G internally vertex disjoint directed paths from s to u and from s to v. We show how to characterize junctions in directed acyclic graphs. We also consider the two problems in the following and derive efficient algorithms to solve them. Given a directed acyclic graph G and a vertex s in G, how can we find all pairs of vertices of G such that s is a junction of them? And given a directed acyclic graph G and k pairs of vertices of G, how can we preprocess G such that all junctions of k given pairs of vertices could be listed quickly? All junctions of k pairs problem arises in an application in Anthropology and we apply our algorithm to find such junctions on kinship networks of some brazilian indian ethnic groups.