Partial words are sequences over a finite alphabet that may have holes that match, or are compatible with, all letters in the alphabet;
partial words without holes are simply words. Given a partial word *w*, we denote by *sub _{w}(n)* the set of subwords of

*w*of length

*n*, that is, words over the alphabet that are compatible with factors of

*w*of length

*n*. We call a set

*S*of words

*h*-representable if

*S = sub*for some integer

_{w}(n)*n*and partial

*w*with

*h*holes. Using a graph theoretical approach, we show that the problem of whether a given set is

*h*-representable can be decided in polynomial time. We also investigate other computational problems related to our new concept of representability.

Keywords: Combinatorics on words; Partial words; Subword complexity; Representable sets.