Семинар лаборатории теоретической информатики: "Positive Aging Admits Fast Asynchronous Plurality Consensus" M. Krnc, "Generalizations of simplicial vertices and a new polynomially solvable case of the maximum weight clique problem" M.Milanic

21 августа на семинаре лаборатории теоретической информатики выступят 2 докладчика. 
Обратите внимание ,что семинар пройдет на Мясницкой, 20, ауд. 445 с 16:40 до 19:30.
Для заказа пропуска пишите dchernyshova@hse.ru.

Matjaž Krnc "Positive Aging Admits Fast Asynchronous Plurality Consensus"
We study the problem of distributed plurality consensus among nodes, each of which initially holds one of opinions. The goal is to eventually agree on the initially dominant opinion. We consider the synchronous communication model in which each node is equipped with a random clock. If the clock of a node ticks, it may open communication channels to a constant number of other nodes, chosen uniformly at random or from a list of constantly many node addresses acquired in some previous steps. The tick rates and the time delays for establishing communication channels (channel delays) follow some probability distribution. Once a channel is established, communication between nodes can be performed atomically.
Previously, asynchronous plurality consensus has mostly been considered in the Poisson clock model (or similar) without any channel delays. We consider distributions for the waiting times between ticks and channel delays that have constant mean and the so-called positive aging property. In this more general setting asynchronous plurality consensus is fast: if the initial bias between the largest and second largest opinion is at least, then after time steps all but a fraction of nodes have the initial majority opinion. Here denotes the initial ratio between the largest and second largest opinion. After additional steps all nodes have the same opinion w.h.p., and this result is tight.
Next, we further improve partial consensus in the case when the distributions mentioned above satisfy an additional property, which is common in many well-known distributions (e.g., exponential, Rayleigh or Weibull with shape parameter at least). In particular, we show that positive aging together with this property leads to consensus time for all but nodes, w.h.p. For a large range of initial configurations, this result implies that partial consensus can be reached significantly faster in this asynchronous communication model than in the synchronous setting with the same limitations on the number of communication partners per time step.
To obtain these results, we first apply our approach in the classical synchronous model. Then, we focus on the asynchronous model: first, we assume the existence of a centralized leader and finally we present two fully distributed algorithms, which do not rely on any predefined leader.

Martin Milanic "Generalizations of simplicial vertices and a new polynomially solvable case of the maximum weight clique problem"
A vertex in a graph is simplicial if its neighborhood forms a clique. In the talk I will discuss three generalizations of the concept of simplicial vertices: avoidable vertices (also known as OCF-vertices), simplicial paths, and their common generalization avoidable paths. A general conjecture on the existence of avoidable paths will be presented, which, if true, would imply results due to Ohtsuki, Cheung, and Fujisawa from 1976 and due to Chvátal, Sritharan, and Rusu from 2002. In turn, both of these results generalize Dirac's classical result on the existence of simplicial vertices in chordal graphs. Very recently (on August 13, 2019) Marthe Bonamy, Oscar Defrain, Meike Hatzel, and Jocelyn Thiebaut announced a proof of the conjecture on arXiv.
An application of the concept of avoidable vertices to the maximum weight clique problem will be presented. A graph is said to be hole-cyclically orientable if it has an orientation such that every induced cycle of length at least four is oriented cyclically. These graphs form a generalization of the class of 1-perfectly orientable graphs and their subclasses chordal graphs and circular-arc graphs. By showing that Lex-BFS computes a bisimplicial elimination ordering on these graphs, which is simultaneously a circular-arc elimination ordering, we derive an efficient algorithm that computes a maximum weight clique of a given vertex-weighted hole-cyclically orientable graph. This is the first known polynomial-time algorithm for the maximum clique problem in the class of 1-perfectly orientable graphs.
The existence of avoidable vertices and edges has interesting consequences for highly symmetric graphs: in a vertex-transitive graph every induced two-edge path closes to an induced cycle, while in an edge-transitive graph every three-edge path closes to a cycle and every induced three-edge path closes to an induced cycle.
Joint work with J. Beisegel, M. Chudnovsky, V. Gurvich, and M. Servatius.