Arjun Kulkarni

Pattern Matching in Poset Permutations is NP-Complete

Started Mar. 11, 2022

Abstract or project description

The pattern matching for permutations (PPM) problem is a natural problem of interest in computer science. While it has been proven to be NP-complete, its natural generalization of pattern matching in poset permutations (PMPP) has been understudied in this regard. The generic version of PMPP is straightforward to prove to be NP-complete by reduction to PPM. On the other hand, even basic variants of PMPP such as that where all total orders are rejected are not so naturally reducible to PPM. Thus, we prove variants of PMPP such as these are also NP-complete.