Greedy Matching en grafos ponderados

Question

Supongamos que existe un grafo de aristas ponderadas. Encontraremos un emparejamiento M añadiendo ávidamente la arista de peso máximo y seguiremos hasta que no se puedan añadir más aristas. Necesito demostrar que el peso de este emparejamiento es al menos la mitad del máximo emparejamiento.

Progreso hasta ahora: He estado intentando resolver este problema tomando la diferencia simétrica entre la coincidencia Máxima y la coincidencia codiciosa. Un par de observaciones que tengo son:

1. No puede haber ningún componente en la diferencia simétrica de longitud 1 ya que puede añadirse a cualquiera de las coincidencias y aumentar su tamaño.
2. Si hay un componente de longitud 2, entonces ambos tendrán el mismo peso porque, de lo contrario, la arista pesada tendrá que ir al greedy matching y la más ligera al máximo. Esto no es posible, ya que en ese caso siempre podemos tomar la arista más pesada para el emparejamiento máximo.
3. Para un componente de longitud 3 - siempre habrá dos aristas de coincidencia máxima y una de coincidencia codiciosa porque de lo contrario el peso de la coincidencia codiciosa en ese componente siempre será mayor que la coincidencia máxima y por lo tanto podríamos cambiar la coincidencia máxima para obtener una coincidencia de más peso. Ahora, dejemos que el peso de la arista del emparejamiento codicioso sea G1 y el peso del emparejamiento máximo sea M1 & M2. G1>= M1 && G1>=M2 pero M1+M2 >= G1, de esto podemos ver que G1>=(M1+M2)/2
4. Para una componente general de longitud n - Esta es la parte en la que estoy atascado y no consigo avanzar. Mientras que soy capaz de hacer algunas observaciones para los componentes de longitud superior a 3, pero no han sido capaces de generalizar hasta ahora.

Soy consciente de que hay otros métodos pero me interesa resolverlo con este método. Creo que estoy muy cerca y hay algún teorema de otros campos matemáticos que se puede utilizar para resolver esto, pero no estoy seguro.

Answer 1

Edición: No he visto la palabra "ponderado". Más abajo hay una solución para la versión no ponderada. Lo dejaré sin embargo, ya que proporciona algunas ideas clave para el caso ponderado. En realidad, ¡ya has terminado! Pero aún así lo escribiré todo una vez más en aras de la exhaustividad. También añadiré más detalles para futuros lectores.

Consideramos la diferencia simétrica $\Delta=(M\setminus M')\cup (M'\setminus M)$ donde I denota la máxima coincidencia con $M$ y el emparejamiento codicioso con $M'$ . Como ha utilizado implícitamente, ningún vértice de $(V,\Delta)$ tiene grado $\geq3$ porque esto implicaría la existencia de dos aristas incidentes en $M$ o $M'$ ambos coincidentes. Por lo tanto, este gráfico consiste en:

1. trayectorias de longitud $\geq0$
2. ciclos

Ahora bien, en estos subgrafos, las "pertenencias" de las aristas deben alternarse, de modo que no haya dos aristas incidentes que sean ambas de $M$ o ambos de $M'$ . Esto implica inmediatamente que los ciclos deben ser de longitud par. Obsérvese que $$|M\setminus M'|\leq2|M'\setminus M| \Rightarrow |M|=|M\setminus M'|+|M\cap M'|\leq2|M'\setminus M|+2|M\cap M'|=2|M'| $$ por lo que basta con demostrar la primera desigualdad.

Como has observado, no puede haber ningún camino de longitud 1, porque o bien alguna arista incidente de este camino-arista (en el grafo original) está en la intersección de $M$ y $M'$ (esto significa que no puede pertenecer a ninguna de las dos, contradicción) o todas las aristas incidentes de esta arista están fuera de $M$ o $M'$ (por lo que puede añadirse a cualquiera de los dos, en contradicción con cómo definimos $M$ y $M'$ ). Por lo tanto, sólo nos fijamos en las trayectorias de longitud $\geq2$ y ciclos pares. Obsérvese que, si reducimos la desigualdad a cada componente conexo y luego sumamos todas estas desigualdades, obtenemos la desigualdad deseada. Por lo tanto, sin pérdida de generalidad, tenemos un solo componente.

Este componente $C$ tiene aristas alternas de $M$ y $M'$ por lo que $|M\cap C|=|M'\cap C|$ (el número de aristas es par) o $|M\cap C|=|M'\cap C|+1$ (el número de aristas es impar). Para esto último, utilizamos una generalización de su tercer punto. A saber, si fuera al revés (estas son las dos únicas posibilidades debido a la alternancia), podríamos "voltear" los lados para obtener $M$ más grande, ¡pero era el máximo! Nótese que aquí hay que prestar un poco de atención a por qué se permitiría dar la vuelta a los lados (de forma análoga al caso de las trayectorias de 1).

En cualquier caso, $$|M\setminus M'|\leq|M'\setminus M|+1\leq 2|M'\setminus M|$$ y hemos terminado.

---

Ahora el caso ponderado. En realidad, la mayor parte del argumento se traslada, es decir, los casos son los mismos. De nuevo wlog un componente. En primer lugar, consideremos la arista más pesada $e_1$ del componente $C$ (desempate potencial sobre el orden del algoritmo codicioso). Esto es ciertamente en $M'\setminus M$ porque en el momento en que se consideró, era factible (como cualquier otro "obstáculo" potencial en $C$ es como máximo igual de pesado). Lo mismo ocurre con el segundo $e_2$ - casi, porque está en $M'\setminus M$ o es incidente en $e_1$ . Iterando esto, cada arista en $e_i$ está en $M'\setminus M$ (= factible cuando se consideró) o es incidente con alguna arista en $M'\setminus M$ que tiene más peso que él (por lo que ya estaba en $M'\setminus M$ cuando se considera, de donde $e_i$ fue "rechazada"). En otras palabras, cada arista de $M\setminus M'$ tiene un vecino con más peso que él. Dado que cada $e\in M'\setminus M$ tiene a lo sumo dos vecinos, contamos por este medio cada vecino a lo sumo dos veces, por lo tanto $c(M\setminus M')\leq 2c(M'\setminus M)$ .