The Algorithmic Complexity of Tree-Clique Width

Abstract

Tree-width has been proven to be a useful parameter to design fast and efficient algorithms for intractable problems. However, while tree-width is low on relatively sparse graphs can be arbitrary high on dense graphs. Therefore, we introduce tree-clique width, denoted by tcl(G) for a graph G, a new width measure for tree decompositions. The main aim of such a parameter is to extend the algorithmic gains of tree-width on more structured and dense graphs. In this paper, we show that tree-clique width is NP-complete and that there is no constant factor approximation algorithm for any constant value c. We also provide algorithms to compute tree-clique width for general graphs and for special graphs such as cographs and permutation graphs. We seek to understand further tree-clique width and its properties and to research whether it can be used as an alternative where tree-width fails.