En graf är svagt 2-färgad om noderna är märkta med färger svart och vitt så att varje svart nod är i anslutning till minst en vit nod och vice versa. I detta arbete studerar vi den distribuerade computational komplexiteten av svag 2-färgning i standard LOCAL-modellen av distribuerade datorer, och hur det är relaterat till den distribuerade computational komplexiteten av andra grafproblem. Först visar vi att svag 2-färgning är en minimal distribuerad symmetri-brytande problem för vanliga träd och regelbundna hög-omkrets grafer: om det finns någon icke-trivial lokalt kontrollerbar märkning problem som är lösbar i o(log * n) rundor med en distribuerad graf algoritm i mitten av ett vanligt träd, sedan svag 2-färgning är också lösbar i o(log * n) rundor där. För det andra visar vi en tight nedre gräns av  och (log * n) för den distribuerade computational komplexiteten av svag 2-färgning i vanliga träd; tidigare var bara en lägre gräns av  och (log log * n) känd. Genom minimalitet, samma nedre gräns håller för någon icke-trivial lokalt kontrollerbara problem inne i vanliga träd. Tidigare arbete med distribuerad beräkningskomplexitet. Formellt sett är den datormodell som vi studerar här känd som LOCAL-modellen för distribuerad dator [17, 21] : samma graf spelar den dubbla rollen att vara både den okända indatagrafen och strukturen i datornätverket, noderna motsvarar datorer, kanterna motsvarar kommunikationslänkar, noderna
Mycket nyligen, Balliu et al. REF förfinade vår kunskap i detta avseende genom att bevisa en snäv nedre gräns av  och plog-nq för svag 2-färgning på vanliga träd.
Hardness of minimal symmetry breaking in distributed computing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}