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的解决方案。这意味着，不太可能有一种有效的方法来通过计算机解决它们（即，对于这些问题，不太可能存在多项式时间算法）。当它们仅限于特殊类别时，它们可以解决多项式时间，但是即使在输入图上施加了很多结构，也仍然很难。 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).它们的结构表征具有深远的算法后果。在应用程序中出现的图类类不一定是次要的，它们通常只是遗传性。关于他们的结构怎么说？与少量封闭的类别一样，不可能期望具有巨大的算法后果，这是如此强大的结构结果。此外，正如对几个复杂的遗传图类别的研究已经证明的那样，次要封闭类研究中开发的一组工具不足以更广泛地研究遗传类别。过去50年来一直研究的最著名的遗传班也许是完美的图表。该课程是由伯格（Berge）于1961年介绍的，他是受到交流理论研究的动机。该课程启发了来自不同领域的大量研究。伯格（Berge）著名的强大图形猜想是使用分解定理证明的。该分解定理使用的切割组与次要类别分解的切割组根本不同。还众所周知，可以在多项式时间内识别完美的图。该区域中的关键开放问题是，对于完美的图表，是否有可能通过纯粹的图理论多项式时间算法来解决相关优化问题（集团，稳定集，构图和覆盖顶点的着色和覆盖）。（众所周知，可以使用椭圆形方法间接进行）。诸如此类的具有挑战性的问题激发了拟议的研究。解决它们将需要开发新的工具和技术来更广泛地研究遗传阶层。在过去的几十年中，通过使用分解获得了许多重要的结果，在这种情况下，人们通过将其分解为更简单的部分来获得对复杂结构的理解。现在在结构上可以很好地理解许多非常有趣的遗传阶级，但是对于其中的一些人来说（尤其是那些需要类似于分解完美图的剪切的遗传学）仍然不清楚如何以算法利用其结构。该项目将重点关注几个适当选择的遗传图类的结构和计算研究，以便更普遍地了解遗传阶层的结构，并深入了解计算上可行的界限。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

On rank-width of even-hole-free graphs

关于偶无洞图的秩宽度

DOI：
10.48550/arxiv.1611.09907
发表时间：
2016
期刊：
arXiv e-prints
影响因子：
0
作者：
Adler Isolde
通讯作者：
Adler Isolde

Clique-cutsets beyond chordal graphs

弦图之外的集团割集

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

Graphs with polynomially many minimal separators

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

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

Clique cutsets beyond chordal graphs

弦图之外的派割集