Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
This work addresses a theoretical problem in computer science for researchers in formal language theory and graph algorithms, offering incremental advances by extending techniques to new domains.
The paper tackles the Int_reg-problem for graph problems, which involves determining if a regular language contains any positive instance of a given graph problem, by developing general criteria using automata and formal language techniques. It applies these methods to well-known problems like Vertex Cover and Independent Set, as well as subgraph, graph-edit, and graph-partitioning problems, providing decision procedures.
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.