Uma abordagem exata para o problema k-in-a-tree utilizando programação linear inteira

Chudnovsky e Seymour, em 2006, publicaram um algoritmo que resolve, em tempo polinomial, o problema denominado
Three-in-a-tree: dados um grafo simples e três vértices arbitrários pertencentes a este grafo, verificar se existe uma subárvore induzida que contenha os vértices.
Neste trabalho iremos lidar com uma generalização deste problema, denominada k-in-a-tree. O problema, portanto, consiste em testar, dado um grafo, se existe uma subárvore induzida que contenha k vértices determinados.
Quando o número de vertices fixos é parte da entrada, o problema é conhecidamente NP-Completo.
Quando, ao invés disso, temos um k fixo, a complexidade está aberta para k >= 4, porém existem algoritmos eficientes para casos restritos como grafos livres de garras, grafos de cintura maior igual a k e grafos cordais.
Neste trabalho apresentamos formulações de Programação Linear Inteira para este problema e verificamos experimentalmente que é possível resolver de forma exata instâncias de tamanho moderado a grande.