Una variante interesante del problema de coincidencia máxima

Dado un gráfico $G(V,E)$ , el problema clásico de coincidencia máxima es elegir el subconjunto máximo de aristas $M$ st, para cada arista $(u,v) \in M$ , $d(u)=d(v)=1$ .

¿Alguien ha estudiado la siguiente variante? Para cada arista , mantiene, donde c es una constante. Llamamos a esta restricción una restricción de grado. $(u,v) \in M$ $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$

La restricción clásica es una conjunción en grado con constante 1. La nueva variante es una disyunción en grado con constante . $c$

El problema en ya es como lo muestra Jukka Suomela. Estoy interesado en los posibles algoritmos de aproximación. Un algoritmo codicioso simple es seleccionar el subgrafo de estrella máximo iterativamente hasta que no se pueda seleccionar ningún subgrafo de estrella (es decir, sin borde (una estrella especial)). Pero este algoritmo funciona mal incluso cuando es un árbol cuando . Hay una estrella interna cuyo centro tiene grado , y hay estrellas externas cada centro tiene grado $c=2$ $NP-complete$ $G$ $c=3$ $x$ $x$ $x$ y conectado al centro de la estrella interior. El valor óptimo es seleccionando aristas de cada una de estrellas externas y 2 estrellas externas completas. El valor producido por el algoritmo verde es seleccionando la estrella interna y un borde de cada estrella externa. $2*x+(x-2)*(x-1)$ $x-2$ $x-2$ $x+1*x$

El algoritmo codicioso anterior es aproximación, donde. Quiero encontrar un mejor algoritmo de aproximación de este algoritmo o demostrar su dureza de aproximación. $2\sqrt{n-1}$ $n=|V|$

Además, quiero saber la clase de complejidad de este problema en el marco de la complejidad parametrizada. Tal vez lleva un algoritmo razonable de parámetros fijos.

Muchas gracias por tu comentario y respuesta por adelantado. :-)

cc.complexity-theory ds.algorithms graph-theory co.combinatorics Peng Zhang
fuente

Entonces, si

, ¿desea encontrar una subgrafía que conste de estrellas disjuntas? ¿Y, por ejemplo, en

la solución óptima consiste entonces exactamente en dos estrellas (

aristas)?

c = 1

$c = 1$

K_{n, n}

$K_{n,n}$

2 n - 2

$2n-2$

Jukka Suomela

El caso de

parece estar estrechamente relacionado con el problema del conjunto dominante: en un gráfico con

nodos, puede encontrar una solución con

bordes si tiene un conjunto dominante de tamaño

c = 1

$c=1$

n

$n$

n - k

$n-k$

k

$k$

Jukka Suomela

Si. No

pero

es su instancia. Muchas gracias. Es exactamente lo que quiero preguntar. ¿Alguien ha estudiado esta variante antes? Mi problema actual está en el gráfico bipartito con

c = 1

$c=1$

c = 2

$c=2$

c = 3

$c=3$

Peng Zhang

Bueno, muchas personas han estudiado conjuntos dominantes . :) Difícil de resolver, difícil de aproximar, incluso en gráficos bipartitos. Quiero suponer que el caso de un mayor

no es más fácil ...

c

$c$

Jukka Suomela

Es un poco confuso ver una recompensa asociada a una pregunta con una respuesta aceptada. Hubiera sido mejor emitir la nueva pregunta por separado. desafortunadamente, ahora que has adjuntado una recompensa, no creo que sea posible.

Suresh Venkat

Respuestas:

(Como parece que la conexión no es completamente obvia, escribiré una versión extendida de los comentarios anteriores como respuesta).

Me centraré en el caso de . En ese caso, el problema se puede reformular de la siguiente manera: $c = 2$

Deje ser un gráfico. La tarea es encontrar un máximo de tamaño tal que la siguiente restricción se cumple: para cada , ya sea es incidente a lo sumo ventaja en o es incidente a lo sumo borde en , o en ambos. $G = (V,E)$ $M \subseteq E$ $\{u,v\} \in M$ $u$ $1$ $M$ $v$ $1$ $M$

Equivalentemente:

El subgrafo inducido por tiene que tener la propiedad de que todos los vecinos de un nodo no hoja (grado> 1) son nodos hoja (grado = 1). $M$

Equivalentemente:

El subgrafo inducido por consiste en estrellas con nudos separados. $M$

A continuación, interpretaré los nodos no coincidentes (nodos que no inciden en ningún borde en ) como estrellas con 0 bordes. Por lo tanto, una solución factible divide el conjunto de nodos en estrellas separadas por nodos. $M$

Ahora, si el número de tales estrellas es , entonces el número de aristas en es exactamente : hay nodos de hoja que están conectados a un centro estelar. Por lo tanto, maximizar el número de aristas en es equivalente a minimizar el número de estrellas. $k$ $M$ $n-k$ $n-k$ $M$

Ahora es sencillo ver que tenemos una solución con estrellas de este tipo si tenemos un conjunto dominante de tamaño : $k$ $k$

Supongamos que se nos dan tales estrellas. Luego podemos encontrar un conjunto dominante de tamaño : simplemente tome los centros de las estrellas (en una estrella con 1 borde puede elegir un nodo arbitrariamente). $k$ $k$
Supongamos que se nos da un conjunto dominante con . Entonces podemos simplemente conectar cada nodo en a un nodo en . Estos bordes forman una familia de estrellas. $D$ $|D| = k$ $V \setminus D$ $D$ $k$

Por lo tanto la solución del problema de manera óptima en un determinado gráfico familia es exactamente tan difícil como encontrar un conjunto dominante mínimo en la misma familia gráfico . En particular, el problema es NP-hard incluso en el caso de gráficos bipartitos. $F$ $F$

(Sin embargo, los resultados de (in) aproximabilidad relacionados con conjuntos dominantes no pueden aplicarse directamente aquí. En esencia, hemos cambiado la función objetivo de a .) $\min |D|$ $\max n-|D|$

Jukka Suomela
fuente

Excelente. Los resultados de (in) aproximabilidad relacionados con conjuntos dominantes no pueden aplicarse directamente aquí, al igual que la inviabilidad de aplicar (in) aproximabilidad de la cubierta de vértice a conjuntos independientes.

Peng Zhang

Para

, también es

. Reduciremos

c = 3

$c=3$

N P - c o m p l e t e

$NP-complete$

(G (V, E), c = 2)

$( G(V,E),c=2)$

(G^{'} (V \cup {v}, E \cup {(u, v)}, u \in V), c = 3)

$( G'(V \cup \{v\} , E \cup \{(u,v)\}, u \in V), c=3)$ .

tiene una solución

G

$G$

K

$K$

G^{'}

$G'$

K

$K$

Peng Zhang