Complexity of Partition Problems

这个建议涉及算法图论的共同主题内的几个问题领域。虽然许多标准的算法和优化问题通常是棘手的（即NP完全），但如果输入仅限于某些自然和结构良好的网络（即图和有向图），则有效的算法成为可能。这是特别真实的许多图着色问题和他们的推广和变种在这项研究中研究。目标之一是阐明有助于解决此类问题的结构类型，并确定此类情况。有时，这涉及到证明所研究问题的难处理性（NP完全性），有时则涉及到设计算法，以利用这些网络的特殊结构。这可以采取各种形式，从使用输入的几何表示到使用其递归描述或其他表征。虽然这已经在无向图的情况下进行了很好的探索，我们的方法的新奇将是系统地将重点扩大到有向图。令人惊讶的是，似乎除了少数例外，类比没有得到充分的研究，我们在最近的研究中已经观察到，有趣的新现象可以而且确实出现了。对一般有向图的关注是无向图类（及其相应的专门算法）的当前理论和应用的重要扩展，这是相当成熟和非常成功的。我们的主要重点将是分区问题，典型的（在无向的情况下），如图着色，图同态，矩阵分区等经典概念。研究的结构将被定义为特殊的排序的存在，或特殊的方向的存在，或存在的新的几何表示。此外，我们将研究这种描述的力量，并研究哪些有向图类可以描述这样的特征。

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.