报告主要观点 | Given a triangulation G of a surface, we consider the question of when G contains a spanning subgraph H which is a triangulated sphere with holes. We give a new short proof of a theorem of Nevo and Tarabykin that every triangulation of the torus contains a spanning subgraph which is a triangulated cylinder. For arbitrary surfaces, we prove that every high facewidth triangulation of a surface with h handles contains a spanning subgraph which is a triangulated sphere with 2h holes. We also prove that the number of holes in our theorem is optimal, even for arbitrarily high facewidth triangulations. Our results are motivated by, and have applications for, rigidity questions in the plane. This is joint work with Katie Clinch, Sean Dewar, Niloufar Fuladi, Maximilian Gorsky, Eleftherios Kastis, Atsuhiro Nakamoto, Anthony Nixon and Brigitte Servatius |
报告主要观点 | Distributed networks are prone to errors so verifying their output is critical. Hence, we develop LOCAL certification protocols for graph properties in which nodes are given certificates that allow them to check whether their network as a whole satisfies some fixed property while only communicating with their local network. Most known LOCAL certification protocols are specifically tailored to the problem they work on and cannot be translated more generally. Thus we target general protocols that can certify any property expressible within a certain logical framework. We consider Monadic Second Order Logic (MSO2), a powerful framework that can express properties such as non-k-colorability, Hamiltonicity, and H-minor-freeness. Unfortunately, in general, there are MSO2-expressible properties that cannot be certified without huge certificates. For instance, non-3-colorability requires certificates of size Ω(n2/logn) on general n-vertex graphs (Göös, Suomela 2016). Hence, we impose additional structural restrictions on the graph. We provide a LOCAL certification protocol for certifying any MSO2-expressible property on graphs of bounded treewidth and, consequently, a LOCAL certification protocol for certifying bounded treewidth. That is for each integer k and each MSO2-expressible property Π we give a LOCAL Certification protocol to certify that a graph satisfies Π and has treewidth at most k using certificates of size (logn) (which is asymptotically optimal). Our LOCAL certification protocol requires only one round of distributed communication, hence it is also proof-labeling scheme. Our result improves upon work by Fraigniaud, Montealegre, Rapaport, and Todinca (Algorithmica 2024), Bousquet, Feuilloley, Pierron (PODC 2022), and the very recent work of Baterisna and Chang. |
报告主要观点 | A connectivity function on a finite set $V$ is a symmetric submodular function $f \colon 2^V \to \mathbb{Z}$ with $f(\emptyset)=0$. We prove that finding a branch-decomposition of width at most $k$ for a connectivity function given by an oracle is fixed-parameter tractable, by providing an algorithm of running time $O(\gamma 2^{O(k^2)} n^6 \log n)$, where $\gamma$ is the time to compute $f(X)$ for any set $X$, and $n = |V|$. This improves the previous algorithm by Oum and Seymour [J. Combin. Theory Ser.~B, 2007], which runs in time $O(\gamma n^{8k+O(1)})$. Our algorithm can be applied to rank-width of graphs, branch-width of matroids, branch-width of (hyper)graphs, and carving-width of graphs. |
Copyright © 世界杯足球(FIFA World Cup)申办官方网站 版权所有 建设与运维：信息网络技术中心 西安聚力