Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Remila, E., & Todinca, I. (2023). Local certification of graphs with bounded genus. Discret Appl. Math., 325, 9–36.
Abstract: 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 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 (centralized) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corol-lary, there is a dMAM(O(log n)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus.We show that there exists a distributed interactive protocol for recognizing 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 non-orientable 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 schn 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 non-orientable genus.
|
Ortiz, C., & Villanueva, M. (2012). Maximal independent sets in caterpillar graphs. Discret Appl. Math., 160(3), 259–266.
Abstract: A caterpillar graph is a tree in which the removal of all pendant vertices results in a chordless path. In this work, we determine the number of maximal independent sets (mis) in caterpillar graphs. For a general graph, this problem is #P-complete. We provide a polynomial time algorithm to generate the whole family of mis in a caterpillar graph. We also characterize the independent graph (intersection graph of mis) and the clique graph (intersection graph of cliques) of complete caterpillar graphs. (C) 2011 Elsevier B.V. All rights reserved.
|
