Todelt dimension

I grafteori og kombinatorisk optimering er den todelte dimension eller biklik-dækningsnummeret for en graf G = ( V , E ) det mindste antal bicliques (det vil sige komplette todelte subgrafer), der kræves for at dække alle kanterne af E. Sættet af bicliques, der dækker alle kanter i G , kaldes kantbiclique-omslaget eller blot biclique-omslaget . Den todelte dimension af en graf G er ofte betegnet med symbolet d ( G ).

Eksempel

Et eksempel på kantdækning ved bi-klik er givet i følgende diagrammer:

Et eksempel på kantdækning med bicliques
Todelt graf...
...og dækker grafen med fire bicliques
rødt biklika cover
blåt biclick cover
grønt biclick cover
sort biclick cover

Todelte dimensionsformler for nogle grafer

Bi -klikdimensionen af en komplet graf med n toppunkter er . $K_n$ $\lceil \log _{2}n\rceil$

Den todelte dimension af en krone med 2n hjørner er , hvor $\sigma(n)$

\sigma (n)=\min \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\}

er den omvendte funktion af den centrale binomiale koefficient [1] . Fishburne og Hammer [2] definerede todelte dimensioner for nogle specielle grafer. For eksempel har en sti en dimension på , mens en løkke har en dimension på . $P_{n}$ $d(P_{n})=\lgulv n/2\rgulv$ $C_{n}$ $d(C_{n})=\lceil n/2\rceil$

Beregning af todelte dimensioner

Problemet med at bestemme den todelte dimension for en given graf G er et optimeringsproblem . Løsningsproblemet for den todelte dimension kan omformuleres som følger:

GIvet: En graf og et positivt heltal .

G=(V,E)

k

SPØRGSMÅL: Indeholder G en biclique-belægning af kanter med en maksimal biclique?

k

Dette problem er indeholdt under nummeret GT18 i den klassiske bog om NP -fuldstændighed af Garey og Johnson [3] og er en direkte omformulering af et andet løselighedsproblem på familier af endelige mængder.

Det grundlæggende sæt-problem er indeholdt under nummeret SP7 i samme bog. Her får vi en familie af delmængder af en endelig mængde , grundmængden for er en anden familie af delmængder af mængden , sådan at enhver mængde fra kan repræsenteres som foreningen af nogle grundlæggende elementer fra . Det grundlæggende sæt problem er nu formuleret som følger: ${\mathcal {S}}=\{S_{1},\ldots ,S_{n}}\}$ ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {B}}=\{B_{1},\ldots ,B_{\ell }\}$ ${\mathcal {U}}$ $S_{i}$ ${\mathcal {B}}$

GIvet: En endelig mængde , en familie af delmængder af mængden og et positivt heltal k .

{\mathcal {U}}

{\mathcal {S}}=\{S_{1},\ldots ,S_{n}}\}

{\mathcal {U}}

SPØRGSMÅL: Findes der et basissæt, hvor størrelsen højst er ?

\mathcal{S}

k

I den første formulering blev NP -fuldstændighed bevist af Orlin [4] selv for todelte grafer . NP -fuldstændigheden af det grundlæggende sætproblem blev bevist tidligere af Stockmeyer [5] . Problemet forbliver NP -hårdt, selvom vi begrænser os til todelte grafer, hvis todelte dimension ikke overstiger , hvor n angiver størrelsen af et bestemt problem [6] . Det er dog godt, at problemet kan løses i polynomisk tid på todelte dominofrie grafer [7] (en domino er en stige med højde 3). $O(\log \,\!n)$

Med hensyn til eksistensen af tilnærmelsesalgoritmer, beviste Simon [8] , at problemet ikke kan tilnærmes godt (forudsat P ≠ NP ). Ydermere er den todelte dimension NP -svær at tilnærme for enhver fast , selv for todelte grafer [9] . $|V|^{1/3-\epsilon }$ $\epsilon >0$

Til sammenligning er det at bevise, at et problem er fast-parametrisk løseligt en øvelse i at bygge parametriske reduktionsalgoritmer (som i Donway og Fellows' bog [10] ). Fleischner, Mijuni, Paulusma og Seider [11] gav også specifikke grænser for den resulterende kerne, som i mellemtiden blev forbedret af Nohr, Hermelin, Charlat et al. [12] .

Faktisk, for en given todelt graf med n hjørner, kan det bestemmes i tid , hvor , om den todelte dimension af grafen af tallet k er større eller ej [12] . ${\displaystyle O(f(k))+n^{3))$ ${\displaystyle f(k)=2^{k2^{k-1}+3k))$

Ansøgning

Problemet med at bestemme den todelte dimension af en graf opstår i forskellige beregningsmæssige sammenhænge. For eksempel i computersystemer kan forskellige brugere af systemet tillades eller nægtes adgang til forskellige ressourcer. I rollebaseret adgangskontrol bestemmer en brugers rolle adgangsrettighederne til et sæt ressourcer. En bruger kan have flere roller og kan få adgang til ressourcer, der er tilgængelige for en af rollerne. En rolle kan til gengæld tildeles flere brugere. Opgaven med at søge efter roller er at tildele et sådant minimumssæt af roller, at de roller, der er tildelt ham, for hver bruger garanterer adgang til alle de ressourcer, som brugeren har brug for. Sættet af brugere, sammen med sættet af ressourcer, definerer naturligvis en todelt graf, hvis kanter definerer brugernes adgang til ressourcer. Hver biclique i en sådan graf er en potentiel rolle, og den optimale løsning på problemet med at finde roller er præcis den minimale kantdækning af bicliques [13] .

Et lignende scenarie opstår i computersikkerhed , mere specifikt sikker udsendelse . I denne situation er det nødvendigt at sende nogle beskeder til en række modtagere gennem en usikker kanal. Hver besked skal være krypteret med en krypteringsnøgle, som kun er kendt af den modtager, som beskeden sendes til. Hver modtager kan have mange krypteringsnøgler, og hver nøgle sendes til flere modtagere. Opgaven med at vælge det optimale valg af krypteringsnøgler er at finde det minimumssæt af krypteringsnøgler, der vil sikre sikker distribution. Som ovenfor kan problemet modelleres ved hjælp af en todelt graf, hvor den minimale bi-klike kantdækning falder sammen med løsningen på problemet med optimalt valg af krypteringsnøgler [14] .

En anden anvendelse er i biologi, hvor minimal kantdækning af bicliques bruges i den matematiske modellering af humant leukocytantigen (HLA) i serologi [15] .

Se også

Liste over NP-komplette problemer
Antallet af skæringspunkter i grafen , det mindste antal kliker , der kræves for at dække kanterne af graferne

Noter

Litteratur

Jérôme Amilhastre, Philippe Janssen, Marie-Catherine Vilarem. Proceedings of the Eightth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 januar 1997, New Orleans, Louisiana - ACM/SIAM, 1997. - S. 36-42.
Dominique de Caen, David A. Gregory, Norman J. Pullman. 3. Caribbean Conference on Combinatorics and Computing / Charles C. Cadogan. - Institut for Matematik, Universitetet i Vestindien, 1981. - S. 169-173.
Rod Downey, Michael R. Fellows. Parameteriseret kompleksitet. - Springer, 1999. - ISBN 0-387-94883-X .
Alina Ene, William G. Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber, Robert Endre Tarjan. 13. ACM-symposium om adgangskontrolmodeller og -teknologier (SACMAT 2008) / Indrakshi Ray, Ninghui Li. - ACM, 2008. - S. 1-10.
Peter C. Fishburn, Peter Ladislaw Hammer. Todelte dimensioner og todelte grader af grafer // Diskret matematik . - 1996. - T. 160 , no. 1-3 . — s. 127–148 . - doi : 10.1016/0012-365X(95)00154-O .
Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, Stefan Szeider. Dækker grafer med få komplette todelte undergrafer // Teoretisk datalogi . - 2009. - T. 410 , no. 21-23 . — S. 2045–2053 . - doi : 10.1016/j.tcs.2008.12.059 .
Michael R. Garey, David S. Johnson. Computere og intraktabilitet: En guide til teorien om NP-fuldstændighed . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 .
Lee-Ad J. Gottlieb, John E. Savage, Arkady Yerukhimovich. Effektiv datalagring i store nanoarrays // Theory of Computing Systems. - 2005. - T. 38 , no. 4 . — S. 503–536 . - doi : 10.1007/s00224-004-1196-9 .
Hermann Gruber, Markus Holzer. 11. internationale konference om udvikling i sprogteori (DLT 2007) / Terjo Harju, Juhani Karhumäki, Arto Lepistö. - Turku, Finland: Springer, 2007. - T. 4588. - S. 205-216. — (LNCS). - doi : 10.1007/978-3-540-73208-2_21 .
Sylvia D. Monson, Norman J. Pullman, Rolf Rees. En undersøgelse af klike- og biklikedækninger og faktoriseringer af (0,1)-matricer // Bulletin of the ICA. - 1995. - T. 14 . — S. 17–86 .
DS Nau, G. Markowsky, MA Woodbury, DB Amos. En matematisk analyse af humant leukocytantigen-serologi // Mathematical Biosciences. - 1978. - T. 40 . — S. 243–270 . - doi : 10.1016/0025-5564(78)90088-3 .
Igor Nor, Danny Hermelin, Sylvain Charlat, Jan Engelstadter, Max Reuter, Olivier Duron, Marie-France Sagot. Mod/Resc Parsimony Inference . – 2010.
James Orlin. Tilfredshed i grafteori: dækker grafer med kliker // Indagationes Mathematicae . - 1977. - T. 80 , no. 5 . — S. 406–424 . - doi : 10.1016/1385-7258(77)90055-5 .
Guoqiang Shu, David Lee, Mihalis Yannakakis. 20. internationale symposium om parallel og distribueret behandling (IPDPS 2006). — IEEE, 2006.
Hans-Ulrich Simon. Om omtrentlige løsninger til kombinatoriske optimeringsproblemer // SIAM Journal om diskret matematik . - 1990. - T. 3 , udg. 2 . — S. 294–310 . - doi : 10.1137/0403025 .