In this paper we investigate the complexity of some recent reconstructions of Reiter's Default Logic using graph-theoretical structures. It turns out that requiring joint consistency of the justification of the applied ...