Convex geometries and directed paths on three vertices

Abstract

A convexity space is an ordered pair $(V,\mathcal{C})$, where $V$ is an arbitrary set and $\mathcal{C}$ is a family of subsets of $V$, called convex, which contains $\{\varnothing ,V\}$ and is closed under intersections and nested unions of its elements. For any $S\subseteq V$, the convex hull of $S$ is the inclusion-wise minimum convex set $C\in \mathcal{C}$ such that $S\subseteq C$. For a convex set $C\in \mathcal{C}$, an element $p\in C$ is an extreme of $C$ if $p$ does not belong to the convex hull of $C\setminus \{p\}$. A convexity $\mathcal{C}$ defined over $V$ is a convex geometry if any convex set $C\in \mathcal{C}$ is the convex hull of its extreme elements. Given an oriented graph $D=(V,A)$, the family $\mathcal{C}$ of subsets of $V$ is the $\overrightarrow{P_3}$-convexity defined over $D$ if $\mathcal{C}$ is formed by all (convex) sets $C\subseteq V$ such that no vertex $v\in V\setminus C$ is the central vertex of a directed path $P=(u,v,w)$ with $\{u,w\}\subseteq C$, while in the $\overrightarrow{P_3^{\ast }}$-convexity defined over $D$, we have that no vertex $v\in V\setminus C$ is the central vertex of a directed path $P=(u,v,w)$ such that $\{u,w\}\subseteq C$ and $(u,w)\notin A$. In this work, we present necessary and sufficient conditions over an oriented graph $D$ so that the $\overrightarrow{P_3}$-convexity over $D$ is geometric, or the $\overrightarrow{P_3^{\ast }}$-convexity over $D$ is geometric. While the first case implies a polynomial-time algorithm to decide whether the $\overrightarrow{P_3}$-convexity over $D$ is a geometric, we show that it is coNP-complete to decide whether the $\overrightarrow{P_3^{\ast }}$-convexity over $D$ is a convex geometry. We also present a family termed acyclic indifference oriented graphs and demonstrate that deciding whether the $\overrightarrow{P_3^{\ast }}$-convexity in this class is geometric can be solved in polynomial-time.