Egy gráf metszéspontszáma a legkisebb számú elem egy adott gráf véges halmaz metszésponti gráfként való ábrázolásában, vagy ezzel egyenértékűen a gráf összes élének lefedéséhez szükséges legkisebb számú klikk [1] [2] [ 3] .
Legyen F egy halmazcsalád ( F -ben megengedett a halmazok ismétlése ). Ekkor az F metszéspont gráf egy irányítatlan gráf , amelynek F minden tagja egy csúcsa és egy éle van bármely két halmaz között, amelyeknek nincs üres metszéspontja. Bármely gráf ábrázolható metszésponti gráfként [4] . Egy gráf metszéspontja az a legkisebb k szám , amelyre létezik egy olyan típus reprezentációja, amelyre az F halmazok uniójának k eleme van [1] . Az adott számú elemű metszésgráf formájú ábrázolás megtalálásának problémája a metszésgráf bázisának megtalálásának problémája [5] .
A G gráf metszésszámának egy alternatív definíciója a G - ben lévő klikkek legkisebb száma ( G teljes részgráfjai ), amely lefedi G minden élét [1] [6] . Az ezzel a tulajdonsággal rendelkező klikkek halmazát peremklikk lefedettségnek nevezzük , ezért a metszéspontok számát néha peremklikk lefedettségi számnak is nevezik [7] .
A metszéspontok számának és a klikkek általi éllefedettség számának egyenlõsége „egyértelmûnek” bizonyult. Egy irányban tegyük fel, hogy G egy olyan F halmazcsalád metszésgráfja, amelynek U uniója k elemet tartalmaz. Ekkor az U bármely x elemére a G gráf csúcsainak az x -et tartalmazó halmazoknak megfelelő részhalmaza klikket alkot – ennek a részhalmaznak bármely két csúcsa szomszédos, mivel a megfelelő halmazaknak van egy x -et tartalmazó nem üres metszéspontja . Ezen túlmenően a G -beli bármely él benne van az egyik ilyen klikkben, mivel egy él nem üres metszéspontnak felel meg, és egy metszés nem üres, ha tartalmaz legalább egy U elemet . Így G élei lefedhetők k klikkel, U minden elemére egy-egy . A másik irányban, ha a G gráf lefedhető k klikkel, akkor a G gráf minden csúcsa reprezentálható a csúcsot tartalmazó klikkek halmazával [8] .
Nyilvánvaló, hogy egy m élű gráfnak számos metszéspontja van, amelyek nem haladják meg az m -t – bármelyik él klikket alkot, és ezek a klikkek együtt lefedik az összes élt [9] .
Az is igaz , hogy minden n csúcsú gráfnak legfeljebb n 2/4 metszéspontja van . Pontosabban fogalmazva, bármely n csúcsú gráf élei legfeljebb n 2 /4 -es klikkre oszthatók , amelyek vagy egyes élek vagy háromszögek [2] [8] . Ez általánosítja a Mantel-tételt , amely szerint egy háromszög nélküli gráfnak legfeljebb n 2 /4 éle van. Háromszög nélküli gráfok esetén az optimális élkattintás-fedő minden élhez tartozik egy klikk, ezért a metszéspontok száma megegyezik az élek számával [2] .
Még erősebb megkötés lehetséges, ha az élek száma szigorúan nagyobb, mint n 2 /4 . Legyen p az adott G gráfban élekkel nem összekötött csúcspárok száma, t pedig az a szám, amelyre t ( t − 1) ≤ p < t ( t + 1) . Ekkor a G gráf metszéspontjainak száma nem haladja meg a p + t [2] [10] értéket .
Azon gráfokon, amelyek ritka gráfok komplementerei , kevés metszéspontja van – bármely n i csúcsú G gráf metszéspontjainak száma nem haladja meg a 2 e 2 ( d + 1) 2 ln n értéket , ahol e a természetes logaritmus alapja , d a G komplementer gráf maximális foka [11 ] .
Annak ellenőrzése, hogy egy adott G gráfnál a metszéspontok száma nem haladja meg a megadott k számot , NP-teljes feladat [12] [13] [14] . Így egy adott gráf metszéspontszámának kiszámítása NP-nehéz feladat.
A metszéspontok számának kiszámításának problémája azonban fix-paraméteresen megoldható . Vagyis van olyan f függvény , hogy ha a metszéspontok száma egyenlő k számmal , akkor ennek a számnak a kiszámításához szükséges idő nem haladja meg f ( k ) n -beli polinommal való szorzatát . Ez kimutatható, ha megjegyezzük, hogy a grafikonon legfeljebb 2k különálló zárt környék található. Az azonos klikkhalmazhoz tartozó két csúcsnak ugyanazok a szomszédai, majd az egyes zárt környékekre egy csúcs kiválasztásával kialakított gráfnak ugyanannyi metszéspontja van, mint az eredeti gráfnak. Ezért polinomiális időben a bemenet egy kisebb kernelre redukálható , maximum 2k csúcsgal. A visszakövető algoritmus exponenciális futási idővel történő alkalmazása ehhez a kernelhez egy f függvényt eredményez, amely a k [ 15 ] kettős kitevője ] . A k -tól való kettős exponenciális függést nem lehet egyszerű exponenciális függőséggé redukálni egy polinomiális méretű mag kinyerésével, amíg a polinomi hierarchia el nem tűnik [16] , és ha az exponenciális időhipotézis helyes, akkor a kettős exponenciális függés nem kerülhető el, ha kernelt használunk. kitermelés vagy sem [17] .
Hatékonyabb algoritmusok ismertek bizonyos speciális gráfosztályokhoz. Egy intervallumgráf metszéspontjainak száma mindig megegyezik a gráf maximális klikkjeinek számával , ami polinomiális időben számítható [18] [19] . Általánosabban, az akkordgráfok metszéspontjainak száma kiszámítható egy olyan algoritmussal, amely megszerkeszti a gráf csúcsainak kizárási sorrendjét. Minden lépésben minden v csúcshoz egy klikket képezünk a v csúcshoz és szomszédaihoz, és kizárjuk a csúcsot, ha vannak olyan élek, amelyek v -vel esnek, de klikkekkel még nem fednek le [19] .