Properties of locally checkable vertex partitioning problems in digraphs

Abstract

While, for undirected graphs, locally checkable vertex subset and partitioning problems have been studied extensively, the equivalent directed problems have not received nearly as much attention yet. We take a closer look at the relationship between undirected and directed problems considering hardness. We extend some properties that have already been shown for undirected graphs to directed graphs. Furthermore, we explore some of the trivialities in directed problem definitions that do not appear in undirected ones. And finally, we construct and visualize digraph coverings to achieve a deeper understanding of their structure.