Directed graph convexities show contrasting complexity behaviors

The Monophonic Directed Convexities

Computational Complexity

Summary

The paper studies special ways to find groups of related points in directed networks, called monophonic convexities. The authors introduce two types, one easier to check and another much harder, based on different kinds of paths. They show that some problems about these groupings are tough to solve on general networks, but easier on special cases like tournaments. This work helps understand which network properties can be efficiently analyzed depending on the type of directed paths considered.

What this means in practice

A theory result. No direct application yet.

Authors

Júlio Araújo, Ana Karolinna Maia, Thiago Marcilon, Nicolas Nisse, Rudini M. Sampaio

Abstract

Graph Convexity is a topic with many papers in the literature, especially on the $P_3$, geodesic, and monophonic convexities in undirected graphs. Regarding directed graphs, Erd{\H o}s et al. in 1972 and Chartrand and Zhang in 2000 obtained the first results on the $P_3$ and geodesic convexities for directed graphs, respectively. In this paper, we start the investigation of monophonic convexity on directed graphs. We define two convexities, the monophonic and the strong monophonic directed convexities, related to the minimal and the induced directed paths, respectively. We show that deciding whether a set is convex is polynomial-time solvable in the monophonic convexity, but coNP-complete in the strong monophonic convexity. For both convexities, we prove that the hull number is NP-complete even in DAGs. Regarding the monophonic convexity, we prove that the hull number is polynomial time solvable in tournaments, but the interval number is NP-complete in tournaments and also in bipartite oriented graphs.