Pattern Matching in Set Partitions is NP-Complete

Abstract

In this note we show that pattern matching in permutations is polynomial time reducible to pattern matching in set partitions. In particular, pattern matching in set partitions is NP-Complete.

4 pages, comments welcome

References in corpus (1)

• Pattern Avoidance in Set Partitions