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.