Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal certification of graph decompositions and applications to minor-free classes
75
0
0.0
(
0
)
Added by
Laurent Feuilloley
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph $G$ belongs to a given graph class~$mathcal{G}$. Such certifications with labels of size $O(log n)$ (where $n$ is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this work, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor $H$, $H$-minor-free graphs can indeed be certified with labels of size $O(log n)$. We also show matching lower bounds with a simple new proof technique.
rate research
Read More
We study the problem of finding large cuts in $d$-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 + 0.177/sqrt{d})m$, where $m$ is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size $(1/2 + 0.28125/sqrt{d})m$. As a corollary, this shows that in any $d$-regular triangle-free graph there exists a cut of at least this size. Our algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying computational techniques in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of $d$.
A distributed graph algorithm is basically an algorithm where every node of a graph can look at its neighborhood at some distance in the graph and chose its output. As distributed environment are subject to faults, an important issue is to be able to check that the output is correct, or in general that the network is in proper configuration with respect to some predicate. One would like this checking to be very local, to avoid using too much resources. Unfortunately most predicates cannot be checked this way, and that is where certification comes into play. Local certification (also known as proof-labeling schemes, locally checkable proofs or distributed verification) consists in assigning labels to the nodes, that certify that the configuration is correct. There are several point of view on this topic: it can be seen as a part of self-stabilizing algorithms, as labeling problem, or as a non-deterministic distributed decision. This paper is an introduction to the domain of local certification, giving an overview of the history, the techniques and the current research directions.
Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). Janos Pach (1981) answered this question in the negative. We strengthen this result by showing that every countable graph that contains all countable planar graphs must contain (i) an infinite complete graph as a minor, and (ii) a subdivision of the complete graph $K_t$ with multiplicity $t$, for every finite $t$. On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite $n$-vertex subgraph has a balanced separator of size $O(sqrt{n})$. The graph is $mathcal{T}_6boxtimes P_{!infty}$, where $mathcal{T}_k$ is the universal treewidth-$k$ countable graph (which we define explicitly), $P_{!infty}$ is the 1-way infinite path, and $boxtimes$ denotes the strong product. More generally, for every positive integer $t$ we construct a countable graph that contains every countable $K_t$-minor-free graph and has the above key properties. Our final contribution is a construction of a countable graph that contains every countable $K_t$-minor-free graph as an induced subgraph, has linear colouring numbers and linear expansion, and contains no subdivision of the countably infinite complete graph (implying (ii) above is best possible).
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a $mathsf{dMAM}(O(log n))$ protocol for this class, that is, a distributed interactive protocol with $O(log n)$-bit proof size in $n$-node graphs, and three interactions between the (centralizer) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corollary, there is a $mathsf{dMAM}(O(log n))$ protocol for the class of planar graphs, as well as for the class of graphs with bounded genus. We show that there exists a distributed interactive protocol for the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of $O(log n)$ bits. This result also holds for the class of graphs with bounded demi-genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded demigenus.
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. This algorithm leads to linear-time isomorphism algorithms for related graph classes, including Helly circular-arc graphs, Gamma-circular-arc graphs, proper circular-arc graphs and convex-round graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
