Problema Acoperirii cu Varfuri

[•Dexter12]

Buna ziua!
Recent am dat de o problema care mi se pare destul de interesanta, dar nu cred ca am gasit inca varianta optima de rezolvare.
Practic este problema acoperirii unui graf cu noduri astfel incat fiecare muchie sa aiba incidenta cel putin un nod din multimea nodurilor. Acea mutime trebuie sa fie de asemenea de cardinal minim. Stiu deja ca aceasta problema este una NP-completa, iar algoritmul meu arata cam asa. Din cate imi pot da seama functia valid mananca mult timp.

Cod:

#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>

using namespace std;

ifstream cin("input.in");
ofstream cout("output.out");

const int MAXN = 105;
const int oo = (1<<31)-1;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

int st[MAXN], N, M, sol = oo;
pair<int, int> Vertex[MAXN];
bitset<MAXN> inS, Truth;

inline bool Valid(int p) {
    inS.reset();
    for(int i = 1 ; i <= p ; ++ i)
        inS[st[i]] = true;
    for(int i = 1 ; i <= M ; ++ i)
        if( !(inS[Vertex[i].first] || inS[Vertex[i].second]) )
            return false;
    return true;
}

inline void Afisare(int p) {
    for(int i = 1 ; i <= p ; ++ i)
        cout << st[i] << " ";
    cout << "\n";
}

inline void Back(int p) {
        for(int pval = st[p-1] + 1; pval <= N ; ++ pval) {
            st[p] = pval;
            if(sol > p)
                if(Valid(p))
                {
                    sol = p;
                    Truth = inS;
                }
            Back(p+1);
        }
}

int main() {
    cin >> N >> M;
    for(int i = 1 ; i <= M ; ++ i)
        cin >> Vertex[i].first >> Vertex[i].second;
    Back(1);
    cout << sol << "\n";
    for(int i = 1 ; i <= N ; ++ i)
        if(Truth[i])
            cout << i << " ";
    cin.close();
    cout.close();
    return 0;
}

Ma puteti ajuta cu o varianta mai optima de rezolvare?

[•olteanul_george]

hmm..ce zici tu seamana cu problema rmvc ( http://www.infoarena.ro/problema/rmvc ) . Incearc-o pe aia si vezi ce iti iese . Bafta !

[•S7012MY]

Buna ziua!
Recent am dat de o problema care mi se pare destul de interesanta, dar nu cred ca am gasit inca varianta optima de rezolvare.

http://en.wikipedia.org/wiki/Vertex_cover

[•Dexter12]

Am gasit si eu diverse informatii, insa nici un algoritm sau cel putin descrierea lui.

[•olteanul_george]

app..am observat o sursa izbitoarea cu a ta a unui tip care trimite probleme la rmvc . ar trebui sa postezi de pe contul tau 

[•visanr]

app..am observat o sursa izbitoarea cu a ta a unui tip care trimite probleme la rmvc . ar trebui sa postezi de pe contul tau 

Dar cum ai vazut sursa, din moment ce n-ai rezolvat problema? 

[•cont_de_teste]

app..am observat o sursa izbitoarea cu a ta a unui tip care trimite probleme la rmvc . ar trebui sa postezi de pe contul tau 

Dar cum ai vazut sursa, din moment ce n-ai rezolvat problema? 

Pai Radu,eu cam observ 3 conturi fantoma in acest topic(dexter,oltean george si va las pe voi sa va dati seama de al 3-lea).
Oricum,epic fail.

[•Dexter12]

app..am observat o sursa izbitoarea cu a ta a unui tip care trimite probleme la rmvc . ar trebui sa postezi de pe contul tau 

Dar cum ai vazut sursa, din moment ce n-ai rezolvat problema? 

Pai Radu,eu cam observ 3 conturi fantoma in acest topic(dexter,oltean george si va las pe voi sa va dati seama de al 3-lea).
Oricum,epic fail.

I see what you did here!
Si totusi, inca nu mi-a dat nimeni nici un hint concret. Please help!