versão de cobertura máxima do conjunto dominante

Question

O problema do conjunto dominante é:

Dado um $n$ gráfico de vértice $G=(V,E)$, encontre um conjunto $S(\subseteqV)$ de tal modo que $|N[S]|$ é exatamente $n$, onde $$ n [s]: = {x ~ | text {$ x $ ou um vizinho de $ x $ está em $ s $} } $$

Minha dúvida é se o seguinte (problema novo) tem um nome definido na literatura, e se não, qual deveria ser o nome mais apropriado.

Novo problema: Dado um $n$ gráfico de vértice $G=(V,E)$ e um número inteiro $k$ , encontre um conjunto $S(\subseteqV)$ de tamanho $k$ de tal modo que $|N[S]|$ é maximizado.

Para o segundo problema, alguns dos nomes que tenho visto na literatura são cobertura máxima de gráfico;cobertura parcial;conjunto k-dominante (no entanto, exatamente os mesmos nomes também são usados ​​​​em outros contextos).

Answer 1

O problema no qual você deve selecionar $k$ vértices para maximizar o número de vértices dominados é conhecido como problema do conjunto dominante orçado.O problema ou sua variante conectada é estudado pelo menos por Lamprou, Sigalis e Zissimopoulos [1] e Khuller, Purohit e Sarpatwar [2].Também aparece na pesquisa recente de Narayanaswamy e Vijayaragunathan [3].

---

[1] Lamprou, Ioannis, Ioannis Sigalas e Vassilis Zissimopoulos."Dominação Conectada Orçada Melhorada e Dominação Orçada de Vértice de Borda." arXiv preprint arXiv:1907.06576 (2019).

[2] Khuller, Samir, Manish Purohit e Kanthi K.Sarpatwar."Analisando a vizinhança ideal:Algoritmos para problemas de conjuntos dominantes conectados orçados e parciais." Anais do vigésimo quinto Simpósio Anual ACM-SIAM sobre Algoritmos Discretos.Sociedade de Matemática Industrial e Aplicada, 2014.

[3] Narayanaswamy, N.S. e R.Vijayaragunathan."Otimização parametrizada em gráficos incertos - uma pesquisa e alguns resultados". Algoritmos 13.1 (2020):3.