Disimplicial arcs, transitive vertices, and disimplicial eliminations

MARTINIANO EGUÍA; FRANCISCO J. SOULIGNAC

Pirenopolis

Workshop; VI Latin American Workshop on Cliques in Graphs; 2014

Universidade Federal de Goiás

In this talk we consider the problems of finding the disimplicial arcs of a sparse digraph and recognizing some interesting graph classes defined by their existence.  A emph{diclique} of a digraph $G$ is a pair $V o W$ of sets of vertices such that $v o w$ is an arc for every $v in V$ and $w in W$.  An arc $v o w$ is emph{disimplicial} when $N^-(w) o N^+(v)$ is a diclique.  For $E subseteq E(G)$, a sequence $S = v_1 o w_1, ldots, v_k o w_k subset E$ is a emph{disimplicial $E$-elimination scheme ($E$-DES)} when $v_i o w_i$ is disimplicial in $G_k = G setminus {v_1, w_1, ldots, v_k, w_k}$.  If no edge of $E$ is disimplicial in $G_k$, then $S$ is emph{maximal}, while $S$ is emph{perfect} when $G_k$ is empty.In the first part we show that the problem of finding the disimplicial arcs is equivalent, in terms of time and space complexity, to that of locating the transitive vertices.  As a result, an $O(alpha m)$ time and $O(m)$ space algorithm to find the bisimplicial edges of bipartite graphs is obtained, where $m$ and $alpha$ are the number of edges and the arboricity of the input graph, respectively.  This improves upon the previous $O(nm)$ time and $O(m)$ space algorithm for sparse graphs (M.~Bomhoff and B.~Manthey. Bisimplicial edges in bipartite graphs. emph{Discrete Appl. Math.},161(12):1699?1706, 2013.)In the second part, we develop two simple algorithms to build disimplicial elimination schemes.  The first algorithm finds a maximal $E(G)$-DES in $O(min{Deltaeta, m}m)$ time, while the second one finds a maximal $E$-DES in $O(alpha m)$ for any given matching $E$.  Here $Delta$ is the maximum among the degrees of the vertices and $eta leq m^{1/2}$ is the $h$-index of the graph.  Both algorithms can be used to solve the respective problems of finding perfect eliminations schemes of bipartite graphs.  The previous best algorithms for this problem on sparse graphs run in $O(m^2)$ time and $O(nm)$ time, respectively. (M.~Bomhoff. Recognizing sparse perfect elimination bipartite graphs. emph{Lecture Notes in Comput. Sci.} 6651:443--455, 2011.)Finally, we study two classes related to perfect disimplicial elimination digraphs, namely weakly diclique irreducible digraphs and diclique irreducible digraphs.  A digraph $G$ is emph{weakly diclique irreducible} when every arc of $G$ belongs to a diclique that contains a disimplicial arc, while it is emph{diclique irreducible} digraphs as those digraphs in which every maximal diclique has a disimplicial arc.  We show that the former class is related to finite posets, while the latter corresponds to dedekind complete finite posets.