Structure and algorithms for graphs with forbidden induced subgraphs

具有禁止诱导子图的图的结构和算法

• 批准号: RGPIN-2020-03912
• 负责人: Spirkl, Sophie
• 金额: $ 2.48万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=739558
• 关键词: Structure; algorithms; graphs; forbidden; induced

Graphs consist of a finite set (vertices) and connections between them (edges). Many real-world data structures fit into this framework, from airports (two of which are connected if there is non-stop flight between them) to social media accounts (two of which are connected if they are friends on the social media network). Algorithms for graphs shape our everyday experiences. Many airlines use a simple heuristic to increase the variety of in-flight movies by having a different selection for eastbound and westbound flights, since most passengers travel once in each direction. Other problems might require (close to) optimum solutions, making the use of heuristics less feasible. As an example, a company might wish to optimize the variety of advertisements that passengers see at airports. Creating an ad is expensive, and thus the company would like to know how they can use as few different ads as possible to ensure that when no passenger sees the same ad at two airports connected by a non-stop flight. This can be stated in terms of graphs: Given a graph, the goal is to assign a natural number to every vertex such that for every edge, its two vertices have different numbers, and the highest number used is as small as possible. This is known as the Graph Colouring Problem, which is computationally intractable. More generally, graph problems arise often in the context of finding an efficient solution for a system described by connections, but they tend to be intractable when no assumptions are made about the input graph. A central question of the proposed research is the following: Which structural assumptions about input graphs make classic graph problems (such as colouring, maximum stable set, and maximum clique) efficiently solvable? Usually, structural assumptions are formulated as forbidden local patterns (induced subgraphs), and the goal is to deduce a sufficient amount of global information about graphs that avoid these patterns to process them quickly. This gives rise to further questions: Can we give a construction for all graphs in a graph class? Can we show that certain graph parameters depend on each other in this graph class, but not in general? Can we show that there is a common pattern that occurs in all very large graphs in the class? Answers to these questions fit into the larger context of describing what a large structure looks like if it does not contain a specified smaller structure. Seminal results related to this question have been obtained or announced in other areas, such as graph minors and matroid minors. This programme benefits HQP by providing a background that is suitable both for industry and academic careers. While the primary impact of this proposal will be felt in the advancement of knowledge in the fields of graph theory, and theoretical computer science in general, it also has the potential to supply tools for practical uses including transportation networks, social media, and resource allocation and distribution.

图由有限集（顶点）和它们之间的连接（边）组成。许多现实世界的数据结构都适合这个框架，从机场（如果它们之间有直飞航班，其中两个是连接的）到社交媒体帐户（如果它们是社交媒体网络上的朋友，其中两个是连接的）。图形算法塑造了我们的日常体验。许多航空公司使用一种简单的启发式方法来增加飞行中电影的种类，即对东向和西向航班进行不同的选择，因为大多数乘客在每个方向上都只旅行一次。其他问题可能需要（接近）最佳解决方案，使得使用数学不太可行。例如，公司可能希望优化乘客在机场看到的各种广告。制作一个广告是昂贵的，因此该公司想知道他们如何才能使用尽可能少的不同广告，以确保当没有乘客看到相同的广告在两个机场连接的直达航班。这可以用图来表述：给定一个图，目标是为每个顶点分配一个自然数，使得对于每个边，它的两个顶点有不同的数，并且使用的最大数尽可能小。这被称为图着色问题，这是计算上难以解决的。更一般地说，图问题通常出现在为由连接描述的系统寻找有效解决方案的背景下，但当没有对输入图进行假设时，它们往往很棘手。 所提出的研究的一个中心问题是：输入图的结构假设，使经典的图形问题（如着色，最大稳定集，最大团）有效地解决？通常，结构假设被公式化为禁止的局部模式（诱导子图），目标是推导出足够数量的全局信息的图，避免这些模式，以快速处理它们。这就产生了进一步的问题：我们能给出一个图类中所有图的构造吗？我们能否证明在这个图类中某些图参数相互依赖，但一般情况下不依赖？我们能否证明类中所有非常大的图中都存在一个共同的模式？这些问题的答案适合于描述一个大结构在不包含指定的较小结构时的样子的更大背景。与此问题相关的种子结果已经在其他领域获得或公布，如图子式和拟阵子式。该计划通过提供适合行业和学术职业的背景使HQP受益。虽然这一提议的主要影响将体现在图论和理论计算机科学领域的知识进步中，但它也有可能为实际应用提供工具，包括交通网络，社交媒体以及资源分配和分配。