Problema 2

[DavidMoranPomes]

He començat també el problema 2. L'apartat b) està demostrat sense problemes, però tinc una idea d'algoritme per al a) sense puta idea de com trobar el ratio jajajajaja El pdf aquí.

[arnaubadia]

L'Albert Canyelles va donar aquesta solució fa uns dies:

[DavidMoranPomes]

Dons no hi havia issue -.-'

[DavidMoranPomes]

De tota manera estic revisant la solució i falten coses, com demostrar que realment és una 2-aproximació al problema proposat (les aproximacions no necessàriament es mantenen constants amb les reduccions). A més l'apartat (b) no està demostrat, ja que tampoc ha fet una reducció formal a vertex cover.

[DavidMoranPomes]

Vale, he refinat una mica la solució que proposa, i he afegit una formalització de l'apartat (b) que no necessita vertex cover. Us la deixo aquí.

[AsLogd]

Perf. mho miro

[AsLogd]

Eh tio, @DavidMoranPomes. Esta de puto lujo. Ho he entes tot llegint en diagonal en 3 mins. congrats

[DavidMoranPomes]

Thanks! :D

[ghost]

@DavidMoranPomes Pau y yo hemos revisado el apartado b) y no vemos que el número de subconjuntos sea el que indicas. En el caso de que fuera |S| = k tendríamos n sobre k que no es independiente de n.

Hemos estado mirando y en las transparencias de Parametrized algorithms (II) se muestra un vertex cover parametrizado con |S| = k. Podríamos usar ese, verdad?

Complejidad temporal: O(n^O(1) + k^(2k+2)

[DavidMoranPomes]

True! he calculat malament el nombre de subconjunts, ho he fet suposant erroniament que |V| = k. Si podem fer vertex cover amb |S| = k si que ho podriem fer. Ara ho reviso i ho torno a pujar. Mersi!

[ghost]

Però el nombre de subconjunt de mida k no és independent d'n. (n sobre k) = n!/((n-k)!*k!)

[DavidMoranPomes]

Però n sobre k és O(n^k), el cost és polinòmic en n

[DavidMoranPomes]

Ho he arreglat seguint un argument similar al de la demostració de vertex cover a FPT de les transpes. Us ho deixo aquí.

[DavidMoranPomes]

En realitat no ho acabo de veure clar. Aquesta nit hi donaré un altre cop d'ull

[AsLogd]

Una versio alternativa a la reduccio al absurd de la implicacio a l'esquerra de l'apartat a) (per mi una mica mes intuitiva): Sabem que S es vertex cover a G2 => Tota aresta e de E2 va a parar, almenys, a un vertex de S => Si fem G2-S llavors E2 es buit => com que al treure S, E2 es buit, significa que a G-S tot vertex esta a distancia 2 o menys => S es node hub (al treurel ens hem quedat amb tot distancia 2 o menys)

[DavidMoranPomes]

Al final he demostrat que és FPT via Vertex Cover, perque la demostració directa no la veig clara del tot i prefereixo anar sobre segur. Us el deixo aquí.

[AsLogd]

Que es el que et fallava de la versio anterior? Jo ho veia prou be

[DavidMoranPomes]

Nuse, si em demanessis de justificar la correctesa no estic segur de poder-ho fer. En canvi treballant amb Vertex Cover si que te la sé justificar ^^'