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

Alejandro Flores-Lamas

A clique is a subset of vertices from a simple graph $G = (V_G, E_G)$ 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, MD$k$C, from a given graph; i.e., the largest cardinality set. This problem is NP-hard in arbitrary graphs. In this work, we address the MD$k$C 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 MD$k$C set in a tree. Then, we adapted 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 MD$k$C set. Then, during a second traversal (top-bottom) it identifies the vertices that belong to the set. The running time of this algorithm is $O\left( (k + 1) \cdot 2^{\tau + 1}\cdot n\right)$ u.t., where $k$ comes from the MD$k$C problem, while $\tau$ and $n$ are the treewidth and order of $G$, respectively.

 Overview  Program