Linear time algorithm for the vertex-edge domination problem in convex bipartite graphs

Abstract

Given a graph G = ( V , E ) , a vertex u E V ve-dominates all edges incident to any vertex in the closed neighborhood N[u]. A subset D c V is a vertex-edge dominating set if, for each edge e E E , there exists a vertex u E D such that u ve-dominates e . The objective of the ve-domination problem is to find a minimum cardinality ve-dominating set in G . In this paper, we present a linear time algorithm to find a minimum cardinality ve-dominating set for convex bipartite graphs, which is a superclass of bipartite permutation graphs and a subclass of bipartite graphs, where the ve-domination problem is solvable in linear time and NP-complete, respectively. We also establish the relationship y ve = i v e for convex bipartite graphs. Our approach leverages a chain decomposition of convex bipartite graphs, allowing for efficient identification of minimum ve-dominating sets and extending algorithmic insights into ve-domination for specific structured graph classes.