Structure of Hereditary Graph Classes and Its Algorithmic Consequences

遗传图类的结构及其算法结果

• 批准号: EP/N019660/1
• 负责人: K Vuskovic
• 金额: $ 72.68万
• 依托单位: University of Leeds
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2016
• 资助国家: 英国
• 起止时间: 2016 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FN019660%2F1
• 关键词: Structure; Hereditary; Graph; Classes; Its

Developing efficient algorithms for solving combinatorial problems is of great importance to the modern technological society. Many problems arising in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc., when modeled by graphs reduce to problems such as finding the size of a largest clique (which is a set of nodes that are all pairwise adjacent), or stable set (which is a set of nodes none of which are pairwise adjacent), or the coloring problem (i.e. using the minimum number of colors to color the vertices of a graph so that no two adjacent vertices receive the same color). Unfortunately these fundamental optimization problems, and many others essential for wide spectrum of applications, are NP-hard to solve in general. This means that it is highly unlikely that there will ever be an efficient way to solve them by a computer (i.e. it is unlikely that polynomial time algorithms exist for these problems). They become polynomial time solvable when restricted to special classes, but also remain difficult even when seemingly quite a lot of structure is imposed on an input graph. Understanding structural reasons that enable efficient algorithms for combinatorial problems on hereditary graph classes (i.e. those closed under vertex deletion) is the primary interest of this proposal.Robertson and Seymour, in their famous Graph Minors Project, elucidated the structure of graph classes that are closed under vertex deletion, and deletion and contraction of edges (i.e. minor-closed). Their structural characterization had far-reaching algorithmic consequences. The graph classes that appear in applications are not necessarily minor-closed, they are more generally just hereditary. What can be said about their structure? It is unlikely to expect such strong structural results with sweeping algorithmic consequences, as was the case with minor-closed classes. Furthermore, as was already evidenced by the study of several complex hereditary graph classes, the set of tools developed in the study of minor-closed classes does not suffice to study hereditary classes more generally. Perhaps the most famous hereditary class, that has been studied for the past 50 years, is the class of perfect graphs. The class was introduced by Berge in 1961, who was motivated by the study of communication theory. This class inspired an enormous amount of research from different fields. Berge's famous Strong Perfect Graph Conjecture was proved using a decomposition theorem. This decomposition theorem uses cutsets that are fundamentally different from the ones used in the decomposition of minor-closed classes. It is also known that perfect graphs can be recognized in polynomial time. The key open problem in the area is whether it is possible, for perfect graphs, to solve the related optimization problems (clique, stable set, coloring and covering of vertices by cliques) by purely graph-theoretical polynomial time algorithms. (It is known that it can be done indirectly, using the ellipsoid method). Challenging problems like these motivate the proposed research. Solving them will require development of new tools and techniques to study hereditary classes more generally.In the past few decades a number of important results were obtained through use of decomposition, where one gains an understanding of a complex structure by breaking it down into simpler parts. A number of very interesting hereditary classes are now structurally well understood, but for some of them (and in particular those that need cutsets similar to the ones used to decompose perfect graphs) it is still not clear how to exploit their structure algorithmically. This project will focus on the structural and computational study of several appropriately chosen hereditary graph classes, with the aim of gaining the insight into the structure of hereditary classes more generally, and an insight into boundary of what is computationally feasible.

开发解决组合问题的有效算法对于现代技术社会非常重要。在交通、电信、分子生物学、工业工程等不同领域中出现的许多问题，当用图建模时，可以简化为诸如寻找最大团的大小（这是一组全部成对相邻的节点）或稳定集（这是一组没有任何成对相邻的节点）或着色问题（即使用最少数量的颜色来对顶点进行着色）的问题。 一个图，以便没有两个相邻顶点接收相同的颜色）。不幸的是，这些基本的优化问题，以及许多其他对于广泛应用至关重要的问题，一般来说是 NP 难解决的。这意味着计算机不太可能有一种有效的方法来解决这些问题（即，不太可能存在针对这些问题的多项式时间算法）。当仅限于特殊类时，它们变得多项式时间可解，但即使在输入图上施加了看似相当多的结构，它们仍然很困难。理解遗传图类（即在顶点删除下封闭的）组合问题的有效算法的结构原因是该提案的主要兴趣。Robertson 和 Seymour 在他们著名的图次要项目中，阐明了在顶点删除以及边的删除和收缩（即次要封闭）下封闭的图类的结构。它们的结构表征具有深远的算法影响。应用程序中出现的图类不一定是小封闭的，它们更一般地只是遗传的。关于它们的结构可以说些什么？不太可能预期如此强大的结构结果会带来广泛的算法后果，就像小封闭类的情况一样。此外，正如对几个复杂遗传图类的研究已经证明的那样，在小封闭类研究中开发的工具集不足以研究更普遍的遗传类。也许过去 50 年来人们研究的最著名的遗传类就是完美图类。该课程由 Berge 于 1961 年创立，他受到传播理论研究的启发。这门课激发了来自不同领域的大量研究。伯格著名的强完美图猜想是用分解定理证明的。该分解定理使用的割集与小闭类分解中使用的割集根本不同。众所周知，可以在多项式时间内识别完美的图。该领域的关键开放问题是，对于完美图，是否有可能通过纯图论多项式时间算法来解决相关的优化问题（团、稳定集、团的着色和顶点覆盖）。 （众所周知，可以使用椭球法间接完成）。此类具有挑战性的问题激发了拟议的研究。解决这些问题需要开发新的工具和技术来更广泛地研究遗传类别。在过去的几十年中，通过使用分解获得了许多重要的结果，即通过将复杂的结构分解为更简单的部分来理解复杂的结构。现在，许多非常有趣的遗传类在结构上已经得到了很好的理解，但对于其中一些（特别是那些需要类似于用于分解完美图的割集的类），仍然不清楚如何在算法上利用它们的结构。该项目将重点关注几个适当选择的遗传图类的结构和计算研究，目的是更广泛地了解遗传类的结构，并深入了解计算上可行的边界。

项目成果

On rank-width of even-hole-free graphs

关于偶无洞图的秩宽度

• DOI: 10.48550/arxiv.1611.09907
• 发表时间: 2016
• 期刊: arXiv e-prints
• 作者: Adler Isolde

Clique-cutsets beyond chordal graphs

弦图之外的集团割集

• DOI: 10.1002/jgt.22428
• 发表时间: 2018
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: Boncompagni V

Clique cutsets beyond chordal graphs

弦图之外的派割集

• DOI: 10.1016/j.endm.2017.10.015
• 发表时间: 2017
• 期刊: Electronic Notes in Discrete Mathematics
• 作者: Boncompagni V

On rank-width of (diamond, even hole)-free graphs

关于无（菱形、偶孔）图的等级宽度

• 发表时间: 2017
• 期刊: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
• 影响因子: 0.7
• 作者: Adler Isolde

Graphs with polynomially many minimal separators

具有多项式多个最小分隔符的图

• DOI: 10.1016/j.jctb.2021.10.003
• 发表时间: 2022
• 期刊: Series B
• 作者: Abrishami, Tara;Chudnovsky, Maria;Dibek, Cemil;Thomassé, Stéphan;Trotignon, Nicolas;Vušković, Kristina
• 通讯作者: Vušković, Kristina