Scrabble on a Graph

Let's play Scrabble on a graph! There are K tiles. Each of the tiles either contains a single uppercase Latin letter or is a blank tile — meaning that it can represent any uppercase Latin letter. Given is also a graph with N nodes and M edges. Initially, some of the nodes contain tiles. The rest of the nodes are unoccupied. Your goal is to construct words from the tiles, by placing them on t