A estrutura técnica nos detalhes.

Dado um grafo G e uma função h que atribui a cada vértice um rótulo em {0, 1, 2, 3, 4}, um vértice é ativo quando seu rótulo é maior que zero. A vizinhança ativa de v, escrita AN(v), é o conjunto dos vizinhos ativos de v.

Subtrair |AN(v)| dos dois lados dá a forma usada na visão geral: cada vizinho ativo contribui com h(u) − 1, isto é, envia tudo menos uma legião, enquanto o próprio vértice contribui com h(v) integral. As duas escritas são a mesma desigualdade.

Um resultado que enxuga o modelo: para todo grafo conexo não trivial existe uma função ótima que não usa o rótulo 1 (Abdollahzadeh Ahangar et al., 2021). Se um vértice recebe 1, é sempre possível zerá-lo e promover um vizinho sem aumentar o peso. Por isso tanto a formulação exata quanto as meta-heurísticas trabalham apenas com {0, 2, 3, 4} — uma variável a menos por vértice.

Os limitantes usados como referência no trabalho: γ_3R(G) ≥ ⌈4n / (Δ+1)⌉ para grafos conexos com Δ ≥ 3 e n ≥ 2 (Valenzuela-Tripodoro et al., 2024), e γ_3R(G) ≤ 3n/2 para grafos conexos com δ ≥ 2 (Hajjari et al., 2023).

• População inicial por heurística: quatro variantes foram comparadas. H1 sorteia um vértice, rotula com 2 e zera a vizinhança; H2 faz o mesmo com rótulo 4 e depois tenta reduzir rótulos; H3 percorre os vértices em ordem decrescente de grau; H4 mistura as três em partes iguais. H4 venceu e define o FLGA.
• Reparo em vez de descarte: cruzamento e mutação produzem soluções inviáveis com frequência. Em vez de rejeitá-las, o procedimento feasibilityCheck percorre os vértices violados e eleva o rótulo ao mínimo que restaura a viabilidade. A população permanece inteiramente viável ao fim de cada geração.
• Redução gulosa: decreaseLabels tenta rebaixar cada rótulo (4 → 3 → 2 → 0) e desfaz a mudança que quebra a viabilidade do vértice ou de sua vizinhança ativa. É o que impede que o reparo acumule folga desnecessária.
• Operadores: seleção por torneio, cruzamento de um ou dois pontos sorteado a cada par, mutação que troca uma posição por um rótulo aleatório e elitismo que preserva ⌈população × taxa⌉ indivíduos.
• Parada: número máximo de gerações ou número máximo de gerações consecutivas sem melhoria — o que ocorrer primeiro.

A implementação segue o Max-Min Ant System dentro do Hyper-Cube Framework: cada vértice carrega um feromônio τ_v ∈ [0,1], iniciado em 0,5 e limitado a [0,001; 0,999].

• Construção: cada formiga escolhe vértices para receber rótulo 4 e zera a vizinhança, até esgotar o grafo auxiliar. A escolha usa deg(u) · τ_u: com probabilidade fixa toma o máximo, senão sorteia por roleta proporcional.
• Estender e reduzir: extendSolution promove uma fração dos vértices a rótulo 4, deliberadamente encarecendo a solução para escapar de mínimos locais; reduceSolution percorre os vértices em ordem decrescente de grau rebaixando rótulos enquanto a viabilidade se mantém.
• Busca local RVNS: destrói uma parcela da solução, reconstrói, estende e reduz. A intensidade da destruição cresce com o nível de vizinhança k, que sobe a cada iteração sem melhoria e volta a 1 assim que uma solução melhor aparece.
• Feromônios guiados pela convergência: o fator φ decide o peso da melhor solução da iteração contra a melhor global — só a da iteração enquanto φ < 0,4, só a global quando φ ≥ 0,8. Se φ passa de 0,99, os feromônios são reinicializados para evitar estagnação.

O gap relativo compara a melhor solução encontrada pelas meta-heurísticas com a solução do modelo exato. O ACO-FL vence na maioria das instâncias, mas a vantagem não é uniforme: em grafos pequenos e densos, e em alguns grafos com muitos ótimos locais, o FLGA chega mais perto.

Nenhuma comparação do trabalho se apoia em impressão: os três critérios abaixo foram declarados antes dos experimentos e aplicados igualmente às duas meta-heurísticas e ao modelo exato.

A partir dessas três métricas, o que o trabalho afirma publicamente:

• Primeira formulação exata correta: o modelo PLI publicado anteriormente aceita soluções inválidas, e o texto exibe o contraexemplo que comprova a falha.
• Primeiras meta-heurísticas para o problema: não havia, até então, abordagem baseada em algoritmos genéticos ou colônia de formigas para a Dominação Romana Tripla.
• Base de instâncias reutilizável: 30 grafos aleatórios gerados com γ_3R exato calculado, além dos valores exatos da maior parte das demais instâncias — material de comparação para pesquisas seguintes.
• Componentes justificados por medição: a busca local RVNS e a heurística de população inicial H4 foram escolhidas por comparação sob o mesmo protocolo, não por preferência.
• Resultado honesto sobre a margem: em 362 grafos avaliados, apenas 6 ficaram a mais de 50% do valor de referência; todos os demais ficaram abaixo desse limiar.

• Nem todo valor de referência é ótimo comprovado. O solver operou com limite de 900 segundos por instância. Sem o asterisco, o valor da coluna PLI é apenas a melhor solução encontrada nesse tempo, e o gap correspondente é uma estimativa por cima.
• Gaps maiores em grafos densos. Quando o ótimo é um número pequeno, como 8, cada legião a mais custa muitos pontos percentuais: os 50% de g200-.8 são a diferença entre 12 e 8. O gap relativo exagera a distância nesses casos.
• Uma execução por instância. As meta-heurísticas são estocásticas e os resultados relatados não vêm de múltiplas execuções com intervalo de confiança, o que impede afirmar diferenças pequenas entre os dois algoritmos.
• Trabalho em aberto. Ampliar a busca de hiperparâmetros, testar outras estratégias de seleção, cruzamento, mutação e elitismo no GA, avaliar outros mecanismos de escolha no ACO e reduzir o tempo de execução por otimizações de implementação.