Solving the distance k-clique problem in 1-outerplanar graphs

Abstract: A clique is a subset of vertices from a simple graph G = (VG, EG) such that each vertex in the set is adjacent to all other vertices in it; in other words, any pair of such vertices are connected with just one edge. Similarly, a distance k-clique is a subset of vertices, from G, such that any pair of vertices in the set are connected with at most k-edges. In this sense, we can express a clique as a distance 1-clique set. A common formulation of these sets as a problem asks to find a Maximum Distance k-Clique, MDkC, from a given graph; i.e., the largest cardinality set. This problem is NP-hard in arbitrary graphs. In this talk, we address the MDkC problem in 1-outerplanar graphs; i.e., graphs that admit a drawing on the plane such that its edges only intersect at the vertices, and each vertex lies on the outer face of the drawing. Our approach to solving this problem was first finding an MDkC set in a tree. Then, we adapt this algorithm to run in 1-outerplanar graphs. The proposed algorithm uses dynamic programming, and it goes through two phases. In the first phase, the algorithm follows a postorder traversal on a tree decomposition of G to compute the size of an MDkC set. Then, during a second traversal (top-bottom) it identifies the vertices that belong to the set.