independent set problem

Angol

Főnév

independent set problem (tsz. independent set problems)

(informatika) Egy gráfban egy független csúcshalmaz (angolul: independent set) olyan csúcshalmaz, amelyben egyik csúcspár sincs éllel összekötve.

Formálisan:

Legyen ${\textstyle G=(V,E)}$ egy gráf.

A ${\textstyle S\subseteq V}$ halmaz független csúcshalmaz, ha:

${\textstyle \forall u,v\in S,(u,v)\notin E}$

❓ A probléma megfogalmazása

Döntési változat:

Input: Egy gráf ${\textstyle G=(V,E)}$ , és egy szám ${\textstyle k}$ . Kérdés: Van-e legalább ${\textstyle k}$ elemű független csúcshalmaz ${\textstyle G}$ -ben?

Ez a k-Független Halmaz Probléma, és NP-teljes.

📊 Példa

Gráf:

A --- B
|     |
C     D

Csúcsok: A, B, C, D
Élek: (A,B), (A,C), (B,D)

Független csúcshalmaz példák:

{C, D}
{B, C}
{A} Mert ezekben nincs olyan pár, amit él összeköt.

📌 Kapcsolódó fogalmak

Fogalom	Leírás
Független halmaz	Olyan csúcshalmaz, ahol nincs él a tagok között
Klikk (clique)	Olyan csúcshalmaz, ahol minden csúcspár össze van kötve
Komplementer gráf	Egy gráf, ahol él ott van, ahol az eredetiben nincs
Maximum független halmaz	A legnagyobb elemszámú független halmaz a gráfban

Megjegyzés: Egy maximum független halmaz keresése egy NP-nehéz optimalizálási probléma.

🧮 Bonyolultság

A független csúcshalmaz probléma NP-teljes.
A maximális független halmaz megtalálása NP-nehéz.
Akkor is nehéz, ha a gráf síkbarajzolható (planáris), vagy szabályos (regular).

🧠 Kapcsolat más problémákkal

Probléma	Kapcsolat
Klikk probléma	Egy gráfban a klikk a komplementer gráf független halmaza
Vertex cover	Egy csúcsfedés és egy független halmaz kiegészíti egymást:
		V \|
Színezési probléma	Színezési osztályok független halmazok

🧠 Algoritmusok

1. Brute force (minden csúcshalmaz kipróbálása)

Időbonyolultság: ${\textstyle O(2^{n})}$

2. Backtracking / Branch and Bound

Hatékonyabb, de még mindig exponenciális

3. Greedy heurisztika

Nem garantál optimális megoldást
Pl. válasszuk a legalacsonyabb fokszámú csúcsot

4. FPT algoritmusok (paraméterezett)

Használhatók, ha a keresett halmaz mérete ${\textstyle k}$ kicsi

⚙️ C++ vázlat – Független halmaz keresése

bool isIndependent(const vector<vector<int>>& adj, const vector<int>& subset) {
    for (int i = 0; i < subset.size(); ++i)
        for (int j = i + 1; j < subset.size(); ++j)
            if (adj[subset[i]][subset[j]])
                return false;
    return true;
}

bool hasIndependentSetOfSizeK(const vector<vector<int>>& adj, int k) {
    int n = adj.size();
    vector<int> nodes(n);
    iota(nodes.begin(), nodes.end(), 0);
    
    for (int mask = 0; mask < (1 << n); ++mask) {
        vector<int> subset;
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i))
                subset.push_back(i);
        if (subset.size() == k && isIndependent(adj, subset))
            return true;
    }
    return false;
}

🧪 Alkalmazások

Vezetéknélküli hálózatok – zavarásmentes pontok kijelölése
Közösségi hálózatok – olyan emberek kiválasztása, akik nem ismerik egymást
Ütemezés – ütközésmentes tevékenységek kiválasztása
Erőforrás-hozzárendelés – konfliktusmentes folyamatok

🧾 Összefoglalás

Fogalom	Leírás
Független halmaz	Csúcshalmaz, ahol nincs él a csúcsok között
Döntési probléma	Van-e legalább ${\textstyle k}$ elemű független halmaz?
Optimalizálási probléma	Legnagyobb elemszámú független halmaz keresése
Bonyolultság	NP-teljes, NP-nehéz
Kapcsolatok	Klikk, vertex cover, gráfszínezés

További információk

independent set problem - Szótár.net (en-hu)
independent set problem - Sztaki (en-hu)
independent set problem - Merriam–Webster
independent set problem - Cambridge
independent set problem - WordNet
independent set problem - Яндекс (en-ru)
independent set problem - Google (en-hu)
independent set problem - Wikidata
independent set problem - Wikipédia (angol)