Avgränsad expansion - Bounded expansion
I grafteori sägs en familj av grafer ha begränsat expansion om alla dess grunda minderåriga är glesa grafer . Många naturliga familjer med glesa grafer har begränsat expansionen. En nära besläktad men starkare egenskap, polynomutvidgning , motsvarar förekomsten av separatorsatser för dessa familjer. Familjer med dessa egenskaper har effektiva algoritmer för problem inklusive isomorfismproblemet och modellkontroll för den första ordningsteorin om grafer.
Definition och motsvarande karakteriseringar
En t -shallow moll av en graf G är definierad att vara en graf bildad från G genom contracting en samling av vertex-disjunkta subgrafer med radien t , och ta bort de återstående hörnen i G . En familj av grafer har begränsat expansionen om det finns en funktion f så att förhållandet mellan kanter och hörn i varje t -grunt mindre av ett diagram i familjen är högst f ( t ).
Motsvarande definitioner av klasser av begränsade utvidgningar är att alla grunda minderåriga har kromatiskt antal avgränsade av en funktion av t , eller att den givna familjen har ett begränsat värde av en topologisk parameter . En sådan parameter är en grafinvariant som är monoton under att ta underbilder, så att parametervärdet endast kan ändras på ett kontrollerat sätt när en graf är uppdelad, och sådan att ett avgränsat parametervärde innebär att en graf har begränsat degenerering .
Polynom expansion och separator satser
En starkare uppfattning är polynomutvidgning , vilket innebär att funktionen f som används för att binda kantdensiteten hos grunda minderåriga är ett polynom . Om en ärftlig graffamilj följer en avskiljarsats och anger att någon n- vertikalgraf i familjen kan delas i bitar med högst n / 2-hörn genom att ta bort O ( n c ) hörn för någon konstant c <1, då att familjen nödvändigtvis har polynomisk expansion. Omvänt har grafer med polynomutvidgning sublinjära separatorsetningar.
Klasser av grafer med begränsad expansion
På grund av sambandet mellan separatorer och expansion har varje mindre stängd graffamilj , inklusive familjen plana grafer , polynomutvidgning. Detsamma gäller för en-plana grafer , och mer allmänt de grafer som kan bäddas på ytor av avgränsas släktet med en begränsad antal korsningar per kant, liksom de biclique fria sträng grafer , eftersom dessa alla lyda liknande separator satser till de plana graferna. I högre dimensionella euklidiska rum , skärningsdiagram av system av bollar med den egenskapen att varje punkt i rymden är täckt av en begränsad antal kulor även obey separator satser som innebär polynom expansion.
Även om diagram med begränsad boktjocklek inte har sublinjära separatorer, har de också begränsad expansion. Andra grafer över begränsad expansion inkluderar grafer över avgränsad grad, slumpmässiga diagram över avgränsad medelgrad i Erdős-Rényi-modellen och diagram över avgränsat könummer .
Algoritmiska applikationer
Instanser av subgrafens isomorfismproblem där målet är att hitta ett måldiagram av begränsad storlek, som ett subgraf av ett större diagram vars storlek inte är avgränsat, kan lösas i linjär tid när det större diagrammet tillhör en familj av grafer av begränsad expansion. Samma sak gäller för att hitta klickarna av en fast storlek, finna dominerande uppsättningar av en fast storlek, eller mer generellt att testa egenskaper som kan uttryckas med en formel av avgränsat storlek i första ordningens logik grafer .
För grafer över polynomutvidgning finns det polynom-tids approximationsscheman för uppsättningen täckproblem , maximalt oberoende uppsättningsproblem , dominerande uppsättningsproblem och flera andra relaterade grafoptimeringsproblem.