Approximate the Clique-Width of a Graph Using Shortest Paths

Abstract

Abstract. In this paper, we present an algorithm to approximate the clique-width of a graph. The proposed approach is based on computing the shortest paths between pairs of vertices. We experimentally show that our proposal approximates the clique-width of simple graphs in polynomial time, while other methods that calculate it in an exact way, transform the problem to SAT, that is well-known as NP-Complete.