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.