Complexity of Partition Problems

点击翻译按钮获取中文摘要

This proposal concerns several problem areas within the common theme of algorithmic graph theory. While many standard algorithmic and optimization problems are intractable (that is, NP-complete) in general, efficient algorithms become possible if the inputs are restricted to certain natural and well-structured networks (that is, graphs and digraphs). This is in particular true for many graph colouring problems and their generalizations and variants studied in this research. One of the objectives will be to illuminate the kind of structure that is helpful for such problems, and identify such situations. Sometimes this involves proving intractability (NP-completeness) of the problems investigated, at other times it involves designing algorithms that take advantage of the special structure these networks posses. This may take various forms, from using a geometric representation of the input, to using its recursive description, or other characterization. While this has been well explored in the case of undirected graphs, the novelty of our approach will be to systematically widen the focus to directed graphs. Surprisingly, it appears that with small exceptions the analogies are not sufficiently well explored, and we have already observed in recent investigations that interesting novel phenomena can and do arise. The focus on general digraphs is a significant extension of the current theory and applications of undirected graph classes (and their corresponding specialized algorithms), which is quite established and very successful. Our main focus will be on partition problems, typified (in the undirected case) by such classical concepts as graph colouring, graph homomorphisms, and matrix partitions. The structures investigated will be defined by the existence of special ordering, or the existence of special orientations, or the existence of novel geometric representations. In addition, we will examine the power of such descriptions, and study which digraph classes can be described by such characterizations.