MISUn algoritmo exacto para el máximo conjunto independiente
BENEMÉRITA UNIVERSIDAD AUTÓNOMA DE PUEBLAMCC 2015Luis Alfredo Moctezuma Pascual
INTRODUCCIÓN
El problema del conjunto independiente máximo de un grafo (MIS) posee una historia relevante en el desarrollo de algoritmos para problemas NP-completos.
Algunas de las últimas mejoras sobre los límites superiores de tiempo para algoritmos exactos corresponden a J. M. Robson con un algoritmo exacto para el cálculo del MIS de un grafo con n nodos y un tiempo de ejecución de O(1.1888n), después, Jianer Chen ha obtenido un algoritmo de tiempo de ejecución de O(1.1254n).
CONJUNTO INDEPENDIENTE
Es un conjunto de vértices(nodo) en un grafo tal que ninguno de sus vértices es adyacente a otro.
Cada arista en el grafo contiene a lo mas un vértice
CONJUNTO INDEPENDIENTE MÁXIMO
Es un conjunto independiente tal que al agregar un vértice mas, deja de ser independiente
CI MAXCI
ALGORITMO
1) Descomponer al grafo quitando el nodo que pertenezca al mayor número de ciclos intersectados. A este nodo lo llamaremos p.
2) Guardar el nodo en una pila que llamaremos ; 3) .4) Repetir esta operación hasta que en el grafo solo quede
algunos de los siguientes tipos:cáctus, bipartito, árbol. A estas descomposiciones finales las llamaremos .
5) Formar un conjunto potencia con los nodos que pertenecen a a este conjunto lo llamaremos S 2
6) Para cada elemento que pertenezca a S 2 , formar un IS con cada uno los (las descomposiciones).
7) El IS con la mayor longitud será el MIS.
EJEMPLO
Sea el grafo G, aplicar el algoritmo propuesto para encontrar el conjunto independiente máximo:
11
1
12
10
9 8
7
53 62 4
1) Descomponer al grafo quitando el nodo que pertenezca al mayor número de ciclos intersectados. A este nodo lo llamaremos p.
Para lograr esto se realiza un recorrido a lo profundo para ubicar cuales son las aristas de retroceso dentro del grafo, para posteriormente hallar los ciclos. Dentro de los ciclos debemos de encontrar a los nodos que pertenezcan al mayor numero de ciclos intersectados.
Ciclo intersectado es aquel que comparte una o más aristas con otro ciclo.
Nodo No. De Ciclos intersectados
1 02 03 24 25 26 07 08 09 0
10 211 212 2
Nodo 4: 2 ciclos, es uno de los nodos con el mayor numero de ciclos intersectados dentro de la tabla, a este nodo lo pasaremos a la pila.
Nota: si existen dos o más nodos que cumplan las dos normas principales, se elige a cualquiera de estos.
Ciclo AristasA 1-2-3-4-5-6-1B 3-4-5-3
C 4-7-8-4
D 1-11-12-10-1
E 11-12-10-11
Nodo 4: 2 ciclos, es uno de los nodos con el mayor numero de ciclos intersectados, a este nodo lo pasaremos a la pila.Si existen dos o más nodos que cumplan las dos normas principales, se elige a cualquiera de estos.
11
1
12
10
9 8
7
53 62 4
Grafo descompuesto
11
1
12
10
9 8
7
53 62
2) Guardar el nodo en una pila que llamaremos ;
S.add(4)S={4}
Esta pila nos servirá para construir el MIS posteriormente y para llevar un control de los nodos que han movido del grafo original
3) .
11
1
12
10
9 8
7
53 62
J : 4NJ:
J : 4NJ:
J : 4NJ:
J : 4NJ:
J : 4NJ:
J :NJ: 4
J :NJ: 4
J : 4NJ:
J : NJ: 4
J : NJ: 4
J : 4NJ:
4) Repetir pasos 1,2 y 3 hasta que en el grafo solo quede algunos de los siguientes tipos:
- cáctus, - bipartito - árbol.
A estas descomposiciones finales las llamaremos .
4) Sub-grafo G1
El sub-grafo es un árbol, por lo tanto ya no le aplicaremos la descomposición y se convertirá en
9 8
7
h1
4.1) Sub-grafo G2, descomponer al grafo quitando el nodo que pertenezca al mayor número de ciclos intersectados. A este nodo lo llamaremos p
11
1
12
10
53 62
NodoNo. De Ciclos intersectados
1 210 211 2
4.1) Sub-grafo G2 descompuesto
11
1
12
53 62
4.2) Sub-grafo G2. Guardar el nodo en una pila ;
S.add(10)S={4,10}
11
1
12
53 62
4.3) Sub-grafo G2. .
11
1
12
53 62
J : 4NJ: 10
J : 4NJ: 10
J : 4NJ: 10
J : 4,10NJ:
J : 10NJ: 4
J : 10 NJ: 4
J : 4,10NJ:
J : 4NJ:
4.4) Sub-grafo G2. Repetir pasos 1,2 y 3 hasta que en el grafo solo quede algunos de los siguientes tipos:cáctus, bipartito, árbol
El sub-grafo es un grafo cactus, por lo tanto ya no le aplicaremos la descomposición y se convertirá en
11
1
12
53 62
h2
5) Formar un conjunto potencia con los nodos que pertenecen a a este conjunto lo llamaremos S 2
6) Para cada elemento que pertenezca a S 2 , formar un IS(conjunto independiente) con cada uno los (las descomposiciones).
11
1
12
53 62
J : 4NJ: 10
J : 4NJ: 10
J : 4NJ: 10
J : 4,10NJ:
J : 10NJ: 4
J : 10 NJ: 4
J : 4NJ:
9 8
7J :NJ: 4
J : 4NJ:
J : NJ: 4
𝒉𝟐
𝒉𝟏
S^2 H1 H2 IS8,9 12,2,5 8,9,12,2,5
4 9 11,6,2 4,9,11,6,210 9,8 2,5 10,9,8,2,5
4,10 9 2,6 4,10,9,2,6
6) Para cada elemento que pertenezca a S 2 , formar un IS(conjunto independiente) con cada uno los (las descomposiciones)
7. El IS con la mayor longitud será el MIS
En este caso todos los IS tienen cardinalidad de 5, por lo que todos son un MIS valido.
RESULTADO 1: caso
MIS={8,9,12,2,5}
11
1
12
10
9 8
7
53 62 4
RESULTADO 2: caso 4
MIS={4,9,11,6,2}
11
1
12
10
9 8
7
53 62 4
RESULTADO 3: caso 10
MIS={10,9,8,2,5}
11
1
12
10
9 8
7
53 62 4
RESULTADO 4: caso 4,10
MIS={4,10,9,2,6}
11
1
12
10
9 8
7
53 62 4
Coloreo de grafo
MIS={4,10,9,2,6}
11
1
12
10
9 8
7
53 62 4
Coloreo de grafo
MIS={4,10,9,2,6}
11
1
12
10
9 8
7
53 62 4
ANALISIS DE COMPLEJIDAD
En la dimensión de M: esto tiene a lo más 2|S| renglones.
El número de columnas en M es k+1 el número de diferentes componentes biconexas de G en la descomposición de Dc(G) = mas 1.
Todos los cálculos para determinar los valores para ser almacenados en la matriz M pueden ser hechos en tiempo polinomial de n. Entonces el tiempo total de la complejidad es de orden O(2|S| · poly(n, m)).
CONCLUSIONES
El algoritmo no construye el árbol-de expansión del grafo de entrada, en lugar de eso calculamos el parámetro k = | S | en una forma eficiente.
Esto nos propone la existencia de un algoritmo eficiente de parámetro fijo para resolver el problema del MIS.