2022/12/09 by Guozhen Rong, Rong, Guozhen, Yongjie Yang +3
Computer Science · #Algorithms and Data Compression #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2212.04880
openalex publication_date 2022/12/09 · openalex created_date 2022/12/25 · openalex updated_date 2026/07/28
We study the partial search order problem (PSOP) proposed recently by Scheffler [WG 2022]. Given a graph G together with a partial order over the set of vertices of G, this problem determines if there is an S-ordering that is consistent with the given partial order, where S is a graph search paradigm like BFS, DFS, etc. This problem naturally generalizes the end-vertex problem which has received much attention over the past few years. It also generalizes the so-called F-tree recognition problem which has just been studied in the literature recently. Our main contribution is a polynomial-time dynamic programming algorithm for the PSOP of the maximum cardinality search (MCS) restricted to chordal graphs. This resolves one of the most intriguing open questions left in the work of Scheffler [WG 2022]. To obtain our result, we propose the notion of layer structure and study numerous related structural properties which might be of independent interest.