2020/03/12 by Petra Wolf, Henning Fernau, Wolf, Petra +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computation and Language (cs.CL) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2003.05826
openalex publication_date 2020/03/12 · openalex created_date 2020/03/23 · openalex updated_date 2026/07/28
The Intreg-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 Intreg-problem for a number of different graph problems and give general criteria that give decision procedures for these Intreg-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 Intreg-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.