The problem of finding the minimum vertex cover is NP-complete [25]. But usually the number of indel events is small (smaller than 50), when the size of the MSA is restricted to the size of a domain (which is usually at most 70 amino acids long). Vertex cover problems of this magnitude can be readily solved, there is a fixed parameter tractable algorithm [27] to solve the problem deterministically, when parameterized by the size of the vertex cover [26,29]. With this algorithm, conflict graphs with minimum vertex covers of size larger than 150 can be resolved in reasonable time. A more detailed version of the paper can be obtained at