Versión máxima de cobertura de Dominating Set

Question

El problema de conjunto dominante es:

Dado un $ n $ el gráfico de vértice $ g= (v, e) $ , encuentre un Establezca $ s (\ subsetaq v) $ tal que $ | n [s] | $ es exactamente < Span Class="Math-contenedor"> $ n $ , donde $$ n [s]:={x ~ | \ Text {ya sea $ x $ o un vecino de $ x $ se encuentra en $ s $} \} $$

Mi pregunta es si el siguiente (nuevo problema) tiene un nombre definido en la literatura, y si no es lo que debería ser el nombre más apropiado.

Nuevo problema: Dado un $ n $ el gráfico de vértice $ g= (v, E) $ y un entero $ k $ , encuentre un conjunto $ s (\ subesteideq v) $ < / SPAN> de tamaño $ k $ tal que $ | n [s] | $ se maximiza. < / p>

Para el segundo problema, algunos de los nombres que he visto en la literatura son la cobertura máxima de gráficos; cobertura parcial; K-Dominating-Set, (sin embargo, los mismos nombres exactamente también se utilizan en otros contextos).

Answer 1

El problema en el que debe seleccionar $ k $ vértices para maximizar el número de vértices dominados se conoce como el problema del conjunto de dominación presupuestado de . El problema o su variante conectada se estudia al menos por Lamprou, Sigalis y Zissimopoulos [1] y Khuller, Purohit y Sarpatwar [2]. También aparece en la reciente encuesta de Narayanaswamy y Vijayaragunathan [3].

---

[1] Lamprou, Ioannis, Ioannis Sigalas y Vassilis Zissimopoulos. "Mejora de la dominación conectada presupuestada y la dominación de vértices de borde presupuestado". Arxiv Preprint ARXIV: 1907.06576 (2019).

[2] Khuller, Samir, Mansish Purohit y Kanthi K. Sarpatwar. "Analizando el vecindario óptimo: algoritmos para problemas de fijación de dominios presupuestados y parciales." Los procedimientos del vigésimo quinto simposio anual ACM-Siam en algoritmos discretos. Sociedad para matemáticas industriales y aplicadas, 2014.

[3] Narayanaswamy, N. S. y R. Vijayaragunathan. "Optimización parametrizada en gráficos inciertos: una encuesta y algunos resultados". Algoritmos 13.1 (2020): 3.