Combinatorics of Mixed Graphs -- Complexity and Homomorphism

图模型是处理关系数据的基本工具;它们使社会科学家能够研究社会网络中不断变化的社会和政治联盟;它们使医学院和医院能够公平地将医疗居民与医院配对;它们使工程师能够为大型工程项目找到有效的时间表。然而，这些模型是有限的，因为它们通常假设一对对象（如人，居民和医院，或任务）之间的关系是相同的，而不管所考虑的对。 在这项研究中，我们研究了一个图模型，允许一个更复杂的概念的关系。例如，研究人员可以使用这样的模型来研究社交网络，其中家庭成员之间的关系被记录为与朋友之间的关系不同的关系。这项研究的长期目标是开发具有这种更复杂的关系概念的图模型工具，以便研究人员和行业可以将这些模型应用于各自的领域。特别是，这项研究的重点是分配问题，在这些问题中，对象分组，或不分组，根据它们之间的关系。分配问题的过去的研究已经导致改进的编译器使用并行处理，在无线电通信网络中的频率分配，并在时间表调度。本研究探讨了关于分配问题的计算性质的基本问题，这些问题定义为具有更复杂关系概念的图模型。它根据有效算法的存在（或怀疑缺乏）来描述这些问题。对于这些问题，预计没有有效的算法可以存在，本研究开发近似算法，算法提供了一个解决方案，保证在一个固定的误差范围内近似的最优解。

Graph models are a fundamental tool for those working with relational data; they allow social scientists to study changing social and political alliances within a social network; they allow medical schools and hospitals a method to fairly pair medical residents with hospitals; and they allow engineers to find efficient schedules for large-scale engineering projects. However, these models are limited in that they often assume that the relationship between a pair of objects (such as people, resident and hospitals, or tasks) is identical, regardless of the pair being considered. In this research we study a graph model that allows for a more sophisticated notion of relationship. For example, using such a model, researchers can study social networks in which the relationship between family members is noted as a different kind of relationship as that between friends. The long-term goal of this research is to develop tools for graph models with this more sophisticated notion of relationship so that researchers and industry may apply these models in their respective areas. In particular, this research focusses on assignment problems; problems in which objects are grouped, or not grouped, based on their relationship to one another. The past study of assignment problems has lead to improvements in compiler use in parallel processing, in frequency assignments in radio communications networks, and in timetable scheduling. This research explores fundamental questions about the computational nature of assignment problems defined for graph models with more sophisticated notions of relationship. It characterizes these problems based on the existence (or suspected lack thereof) of efficient algorithms. For those problems for which it is expected that no efficient algorithm can exist, this research develops approximation algorithms, algorithms that provide a solution that is guaranteed to approximate the optimal solution within a fixed error bound.