¿Se conoce la complejidad de este problema de cobertura?

Deje ser un gráfico. Un conjunto de vértices se llama crítico si y no vértice en es adyacente a exactamente un vértice en . El problema es encontrar un conjunto de vértices de tamaño mínimo tal que para cada conjunto crítico . $G=(V,E)$ $X\subseteq V$ $X\neq\emptyset$ $V\setminus X$ $X$ $S\subseteq V$ $S\cap X\neq\emptyset$ $X$

El problema tiene la siguiente interpretación de difusión de rumores: Vertex difunde el rumor a su vecino si y solo si todos los demás vecinos de ya están informados. La pregunta es, entonces, ¿cuántos vértices tengo que informar inicialmente para asegurarme de que todos estén informados al final? $i$ $j$ $i$

cc.complexity-theory graph-theory co.combinatorics optimization Thomas Kalinowski
fuente

Esto tiene una solución bastante simple, por lo que quizás el problema tenga más condiciones de las especificadas; ignorando el caso especial

y si

está conectado, cada vértice

con grado

tiene un conjunto crítico

asociado a él, de modo que sólo los vecinos de exclusivamente ° 1 vértices pueden estar en

. Si existe tal vértice, entonces

es un gráfico de estrella y su centro (como un singleton) es el

mínimo único . Si

no está conectado, mire cada componente conectado.

X = V

$X=V$

G

$G$

v

$v$

> 1

$>1$

V ∖ {v}

$V\setminus\{v\}$

S

$S$

G

$G$

S

$S$

G

$G$

Joe Bebel

Para una estrella

con

hojas, cada conjunto de dos hojas es crítico y, por lo tanto, la solución óptima es tomar hojas.

K_{1, n}

$K_{1,n}$

n ⩾ 2

$n\geqslant 2$

n - 1

$n-1$

Thomas Kalinowski

Oh, veo mi interpretación errónea

Joe Bebel

Pregunta muy interesante, una pequeña objeción: probablemente desee que sus conjuntos críticos no estén vacíos (de lo contrario, no hay

S

$S$

Klaus Draeger

@JoeBebel: El problema de decisión "¿Existe una solución para establecer

como máximo

?" está en NP. Puede verificar si un conjunto

es una solución mediante el siguiente algoritmo. Si bien no es un vértice

, que tiene exactamente el vecino

exterior

, añadir

. Si

contiene eventualmente todos los vértices, entonces su conjunto inicial fue una solución, de lo contrario, se atascará, y el complemento del conjunto final es un conjunto crítico, por lo que el

inicial no fue una solución.

S

$S$

K

$K$

S

$S$

v \in S

$v\in S$

w

$w$

S

$S$

w

$w$

S

$S$

S

$S$

S

$S$

Thomas Kalinowski

¿Se conoce la complejidad de este problema de cobertura?

Respuestas: