In parsing problems, the variables consist of indices into the string being parsed, and the constraints require that a nonterminal on the right-hand side of a rule has previously been identified.
the graph has a vertex for each endpoint involved in the rule, and a clique for each nonterminal (including the left-hand side nonterminal) connecting all its endpoints.