Recognizing digraphs of Kelly-width 2 ?
Kelly-width is a parameter of digraphs recently proposed by Hunter and Kreutzer as a directed analogue of treewidth. We give an alternative characterization of digraphs of bounded Kelly-width in support of this analogy, and the first polynomial-time algorithm recognizing digraphs of Kelly-width2. For an input digraphG=(V,A) G = ( V , A ) the algorithm outputs a vertex ordering and a digraphH=(V,B) H = ( V , B ) with A?B A ? B witnessing either that G G has Kelly-width at most 2 or that G G has Kelly-width at least 3, in time linear in H H .
kelly-width characterization digraph width parameter recognition