Detecting Induced Graph Patterns

检测诱导图模式

基本信息

批准号：
EP/K025090/1
负责人：
Daniel Paulusma
金额：
$ 46.31万
依托单位：
Durham University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2013
资助国家：
英国
起止时间：
2013 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FK025090%2F1
关键词：
Detecting Induced Graph Patterns

项目摘要

A graph is a network consisting of nodes called vertices and links between those nodes called edges representing some relationship such as individuals that are connected to other individuals in a social network. Graphs are ubiquitous, not only in science and engineering but also in real life, as is the study of whether a given graph H appears as a pattern within another given graph G so that G can be transformed to H via a sequence of operations. For instance, can a social network G be compressed to a smaller (and easier to analyze) network H without destroying too much information? This example shows that the notion of appearing as a pattern depends upon the operations allowed when transforming G into H. We consider the following four elementary graph operations: 1. vertex deletions2. edge deletions3. edge contractions4. vertex dissolutions.A vertex deletion removes a vertex (and its adjacent edges) from the graph. An edge deletion removes an edge from the graph. An edge contraction removes the vertices u and v of the edge (u,v) from the graph and replaces them by a new vertex that is made adjacent to precisely those remaining vertices to which u or v was previously adjacent. A vertex dissolution is the removal of a vertex v from the graph with exactly two neighbours u and w followed by the inclusion of the edge (u,w). Combining these four graph operations leads to ten essential graph containment relations. For example, a graph H is called a minor of a graph G if H can be obtained from G by a sequence of vertex deletions, edge deletions and edge contractions (and so also vertex dissolutions), whereas H is an induced minor of G if we do allow vertex deletions and edge contractions but no edge deletions. Each graph containment relation corresponds to a decision problem: subject to the specified containment relation, does a graph G contain some graph H?In order to answer this question we must design a so-called algorithm, which can be seen as a set of instructions, like a recipe for preparing a meal, but with the purpose to turn it into a computer program to solve the problem automatically. A crucial aspect is the running time, i.e., the time it will take the computer to solve the problem. However, it may well be possible that the problem falls into the category of discrete optimization problems for which no reasonably fast algorithm is known, and for which the existence of such an algorithm is even considered to be unlikely. One of the most important and fundamental achievements of Theoretical Computer Science and Discrete Mathematics is Robertson and Seymour's Graph Minor Project. They have provided a structural characterization of graphs without a forbidden minor and have designed an algorithm that solves any problem H-Minor in cubic time; the latter problem is to decide whether a given graph contains some fixed graph H (i.e., that is not part of the input) as a minor. Their theory has led to deep results across Computer Science and Mathematics. An important consequence of their theory is that any containment problem allowing edge deletions can be efficiently solved. Our over-arching aim is to develop a theory, similar to that of Robertson and Seymour, but on induced containment relations, i.e., when edge deletions are not permitted graph operations. As techniques that are useful for their non-induced counterparts can no longer be applied, a basic theory for induced containment relations, similar to the Graph Minor Project of Robertson and Seymour, is largely absent. Our research proposal aims to change this.

图是一个由称为顶点的节点和称为边的节点之间的链接组成的网络，这些链接表示某种关系，例如与社交网络中的其他个体连接的个体。图不仅在科学和工程中而且在现实生活中无处不在，就像研究给定图 H 是否在另一个给定图 G 中出现为模式，以便可以通过一系列操作将 G 转换为 H 一样。例如，是否可以将社交网络 G 压缩为更小（且更易于分析）的网络 H，而不破坏太多信息？这个例子表明，作为模式出现的概念取决于将 G 转换为 H 时允许的操作。我们考虑以下四种基本图操作： 1. 顶点删除 2. 顶点删除。 3. 边缘删除边缘收缩 4.顶点溶解。顶点删除从图中删除顶点（及其相邻边）。边删除会从图中删除一条边。边收缩从图中删除边 (u,v) 的顶点 u 和 v，并用新顶点替换它们，该新顶点恰好与 u 或 v 先前相邻的剩余顶点相邻。顶点溶解是从图中删除恰好有两个邻居 u 和 w 的顶点 v，然后包含边 (u,w)。组合这四种图操作会产生十种基本的图包含关系。例如，如果 H 可以通过一系列顶点删除、边删除和边收缩（以及顶点分解）从 G 获得，则图 H 被称为图 G 的小图，而 H 是 G 的导出小图，如果我们确实允许顶点删除和边收缩，但不允许删除边。每个图包含关系对应一个决策问题：在指定的包含关系下，图G是否包含某个图H？为了回答这个问题我们必须设计一个所谓的算法，它可以看作是一组指令，就像准备饭菜的菜谱一样，但目的是将其转化为计算机程序来自动解决问题。一个关键方面是运行时间，即计算机解决问题所需的时间。然而，该问题很可能属于离散优化问题的范畴，对于这种问题，还没有相当快的算法是已知的，甚至认为这种算法的存在不太可能。理论计算机科学和离散数学最重要和最根本的成就之一是 Robertson 和 Seymour 的小图项目。他们提供了没有禁止小数的图的结构特征，并设计了一种算法，可以在立方时间内解决任何 H 小数问题；后一个问题是确定给定图是否包含某个固定图 H（即，不是输入的一部分）作为次要图。他们的理论在计算机科学和数学领域取得了深刻的成果。他们的理论的一个重要结论是，任何允许边缘删除的遏制问题都可以得到有效解决。我们的首要目标是发展一种类似于 Robertson 和 Seymour 的理论，但基于诱导包含关系，即不允许进行图操作时的边删除。由于对非诱导对应物有用的技术不再适用，因此基本上不存在诱导包含关系的基本理论，类似于 Robertson 和 Seymour 的图小项目。我们的研究计划旨在改变这一点。