Structure of hereditary graph classes and their consequences

遗传图类的结构及其后果

• 批准号: 2111629
• 金额: --
• 依托单位: University of Leeds
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2018
• 资助国家: 英国
• 起止时间: 2018 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2111629
• 关键词: Structure; hereditary; graph; classes; their

Many important graph-theoretic problems such as minimum vertex colouring, maximum clique, and maximum stable set are NP-complete in general (suggesting that there are likely no polynomial-time algorithms for these problems), but can be solved in polynomial time for certain classes of graphs whose structure can be exploited. For hereditary graph classes (i.e. classes of graphs closed under taking induced subgraphs), we are interested in decomposition theorems: how might we decompose a graph into its basic building blocks such that (1) hard problems can be easily solved on these basic graphs, and (2) the solutions for the basic graphs may be combined to give a solution for the original graph. A simple decomposition theorem where this paradigm works nicely is Dirac's characterisation of chordal graphs, which states that if a graph is chordal then it is either a clique or it has a clique cutset. Possibly the most famous decomposition theorem for hereditary graph classes was published in 2006 by Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas, which resolved a long-standing conjecture of Claude Berge concerning perfect graphs. In particular, it was shown that a graph G is perfect if and only if G contains neither an odd hole nor an odd antihole as an induced subgraph. This gave way to a polynomial-time recognition algorithm for perfect graphs. It is also known that minimum vertex colouring, maximum clique, and maximum stable set can be solved in polynomial time for perfect graphs. However, this algorithm makes use of the ellipsoid method. It remains open whether it is possible to solve these problems in polynomial time using purely combinatorial methods. This research on perfect graphs opened up many other interesting questions about hereditary graph classes, and for instance motivated the study of even- hole-free graphs; a class which is structurally quite similar to the class of perfect graphs. Although polynomial-time algorithms are known for recognising and finding maximum cliques in even-hole-free graphs, the complexity of finding a maximum stable set and a minimum vertex colouring remain open. Towards a greater understanding of the class of even-hole-free graphs we will consider some of its subclasses and try to understand how their structure can be exploited in algorithms.

许多重要的图论问题，如最小顶点着色、最大团和最大稳定集，一般都是NP完全的(这意味着这些问题可能没有多项式时间算法)，但对于某些结构可以利用的图，可以在多项式时间内求解。对于遗传图类(即在取诱导子图下闭合的图类)，我们感兴趣的是分解定理：如何将一个图分解成它的基本构造块，使得(1)在这些基本图上可以很容易地解决困难问题，(2)可以将基本图的解结合在一起给出原始图的解。一个简单的分解定理很好地应用于这个范例，那就是狄拉克对弦图的刻画，该定理指出，如果一个图是弦图，那么它要么是一个团，要么它有一个团割集。关于遗传图类的最著名的分解定理可能是由Maria Chudnovsky，Neil Robertson，Paul Seymour和Robin Thomas于2006年发表的，它解决了Claude Berge关于完美图的长期猜想。特别地，证明了图G是完美的当且仅当图G既不包含奇洞也不包含奇洞作为导出子图。这就让位于完美图形的多项式时间识别算法。对于完全图，最小顶点着色、最大团和最大稳定集可以在多项式时间内求解。然而，该算法使用了椭球体方法。是否有可能用纯组合方法在多项式时间内解决这些问题，目前尚无定论。这项关于完美图的研究提出了许多关于遗传图类的其他有趣的问题，例如，激励了无偶洞图的研究，这类图在结构上与完美图类非常相似。虽然多项式时间算法在无偶洞图中识别和找到最大团是众所周知的，但寻找最大稳定集和最小顶点着色的复杂性仍然是悬而未决的。为了更好地理解这类无偶洞图，我们将考虑它的一些子类，并试图理解它们的结构如何在算法中得到利用。