论文标题
图形问题的常规交点空虚：借助于自动机
Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
论文作者
论文摘要
组合问题P的INT_REG问题P询问，如果M M接受的语言L（M）是否包含问题的任何正面实例。我们考虑了许多不同的图形问题的INT_REG-PROMBREM，并给出了这些INT_REGRBROMBLEMBS的决策程序。为了实现这一目标，我们考虑了一个自然图编码，以便所有图形编码的语言都是常规的。然后，我们从正式的语言理论领域中绘制经典的泵送和互换 - arguments之间的连接，并在编码图上引起了图形操作。我们的技术在其他方面适用于众所周知的图形问题，例如顶点封面和独立集合，以及子图问题，图形编辑问题和图形分区问题，包括着色问题。
The Int_reg-problem of a combinatorial problem P asks, given a nondeterministic automaton M as input, whether the language L(M) accepted by M contains any positive instance of the problem P. We consider the Int_reg-problem for a number of different graph problems and give general criteria that give decision procedures for these Int_reg-problems. To achieve this goal, we consider a natural graph encoding so that the language of all graph encodings is regular. Then, we draw the connection between classical pumping- and interchange-arguments from the field of formal language theory with the graph operations induced on the encoded graph. Our techniques apply among others to the Int_reg-problem of well-known graph problems like Vertex Cover and Independent Set, as well as to subgraph problems, graph-edit problems and graph-partitioning problems, including coloring problems.
