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
- •For network algorithm designers: Design algorithms for directed networks that efficiently detect minimal convex sets when using monophonic convexity.
- •For graph software developers: Avoid relying on strong monophonic convexity checks in directed acyclic graphs due to high computational complexity.
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.