A popular way to define or characterize graph classes is via forbidden subgraphs or forbidden minors. These characterizations play a key role in graph theory, but they rarely lead to efficient algorithms to recognize these classes. In contrast, many essential graph classes can be recognized efficiently thanks to characterizations of the following form: there must exist an ordering of the vertices such that some ordered pattern does not appear, where a pattern is basically an ordered subgraph. These pattern characterizations have been studied for decades, but there have been recent efforts to better understand them systematically. In this paper, we focus on a simple problem at the core of this topic: given an ordered graph of size $n$, how fast can we detect whether a fixed pattern of size $k$ is present? Following the literature on graph classes recognition, we first look for patterns that can be detected in linear time. We prove, among other results, that almost all patterns on three vertices (which capture many interesting classes, such as interval, chordal, split, bipartite, and comparability graphs) fall in this category. Then, in a finer-grained complexity perspective, we prove conditional lower bounds for this problem. In particular we show that for a large family of patterns on four vertices it is unlikely that subquadratic algorithm exist. Finally, we define a parameter for patterns, the merge-width, and prove that for patterns of merge-width $t$, one can solve the problem in $O(n^{ct})$ for some constant~$c$. As a corollary, we get that detecting outerplanar patterns and other classes of patterns can be done in time independent of the size of the pattern.
翻译:用于定义或描述图形类的流行方式是通过被禁止的子集或被禁止的未成年人来定义或描述图形类。 这些特征特征在图形理论中扮演着关键角色, 但很少导致有效的算法来识别这些类。 相反, 许多基本图形类可以通过以下形式的特征来有效地被识别: 必须要有一条螺旋的顺序, 这样某些按顺序排列的图案就不会出现, 这样的图案基本上是一个按顺序排列的子集。 这些模式的特征已经研究了几十年, 但是最近已经做出了一些努力来系统地理解它们。 在本文中, 我们关注这个主题的核心是一个简单的问题: 鉴于一个按顺序排列的大小图案, 美元, 我们如何快速地检测到一个固定的大小 $? 在图形类图案的图案识别中, 我们首先查看一个可以在线性时间中检测到的图案型图案, 几乎所有的图案都能够捕捉到许多有趣的类, 比如间距、 correndal、 bipartite, 和可比性图案的图案。 然后, 在一个精细的图案里, 我们从一个不易变的图案的图案中, 显示一个固定的大小。