On the Computational Complexity of Optimization Convex Covering Problems of Graphs

Abstract

In this paper we present further studies of convex covers and convex partitions of graphs. Let $G$ be a finite simple graph. A set of vertices $S$ of $G$ is convex if all vertices lying on a shortest path between any pair of vertices of $S$ are in $S$. If $3\leq|S|\leq|X|-1$, then $S$ is a nontrivial set. We prove that determining the minimum number of convex sets and the minimum number of nontrivial convex sets, which cover or partition a graph, is in general NP-hard. We also prove that it is NP-hard to determine the maximum number of nontrivial convex sets, which cover or partition a graph.

Keywords

• np-hardness
• convex cover
• convex partition
• graph