Recent zbMATH articles in MSC 68Rhttps://zbmath.org/atom/cc/68R2023-09-22T14:21:46.120933ZUnknown authorWerkzeugNonrepetitive list colorings of the integershttps://zbmath.org/1517.050502023-09-22T14:21:46.120933Z"Bosek, Bartłomiej"https://zbmath.org/authors/?q=ai:bosek.bartlomiej"Grytczuk, Jarosław"https://zbmath.org/authors/?q=ai:grytczuk.jaroslaw"Nayar, Barbara"https://zbmath.org/authors/?q=ai:nayar.barbara"Zaleski, Bartosz"https://zbmath.org/authors/?q=ai:zaleski.bartoszSummary: A coloring of the integers is nonrepetitive if no two adjacent intervals have the same color sequence. A beautiful theorem of Thue asserts that there exists a nonrepetitive coloring of \(\mathbb{N}\) using only three colors. We obtain some generalizations of this result in which the adjacency of intervals is specified by more general graphs. We focus on the list variant of the problem, in which every integer gets a color from its own set of colors. For instance, we prove that there exists a coloring of \(\mathbb{N}\) from arbitrary lists of size 8, such that the following property holds for every \(n\geq 1\): among any \(2^n\) consecutively adjacent intervals, each of length \(n\), no two have the same color sequence. Another result is related to the possible extension of the famous Dejean's conjecture to the list setting. It asserts that for every \(k\geq 1\), there is a coloring of \(\mathbb{N}\) from lists of size \(k+2\sqrt{k}\), such that no two among any \(k\) consecutively adjacent intervals have the same color sequence.Minimum gradation in greyscales of graphshttps://zbmath.org/1517.050532023-09-22T14:21:46.120933Z"de Castro, Natalia"https://zbmath.org/authors/?q=ai:de-castro.natalia"Garrido-Vizuete, María A."https://zbmath.org/authors/?q=ai:garrido-vizuete.maria-a"Robles, Rafael"https://zbmath.org/authors/?q=ai:robles.rafael"Villar-Liñán, María Trinidad"https://zbmath.org/authors/?q=ai:villar-linan.m-tSummary: In this paper we present the notion of greyscale of a graph as a colouring of its vertices that uses colours from the real interval [0,1]. Any greyscale induces another colouring by assigning to each edge the non-negative difference between the colours of its vertices. These edge colours are ordered in lexicographical decreasing ordering and give rise to a new element of the graph: the gradation vector. We introduce the notion of minimum gradation vector as a new invariant for the graph and give polynomial algorithms to obtain it. These algorithms also output all greyscales that produce the minimum gradation vector. This way we tackle and solve a novel vectorial optimization problem in graphs that may generate more satisfactory solutions than those generated by known scalar optimization approaches.Algorithms for the rainbow vertex coloring problem on graph classeshttps://zbmath.org/1517.050572023-09-22T14:21:46.120933Z"Lima, Paloma T."https://zbmath.org/authors/?q=ai:lima.paloma-t"van Leeuwen, Erik Jan"https://zbmath.org/authors/?q=ai:van-leeuwen.erik-jan"van der Wegen, Marieke"https://zbmath.org/authors/?q=ai:van-der-wegen.mariekeSummary: Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. In the \textsc{Rainbow Vertex Coloring (RVC)} problem we want to decide whether the vertices of a given graph can be colored with at most \(k\) colors so that the graph becomes rainbow vertex-connected. This problem is known to be NP-complete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomial-time algorithms for RVC on permutation graphs, powers of trees and split strongly chordal graphs. The algorithm for the latter class also works for the strong variant of the problem, where the rainbow vertex paths between each vertex pair must be shortest paths. We complement the polynomial-time solvability results for split strongly chordal graphs by showing that, for any fixed \(p \geq 3\) both variants of the problem become NP-complete when restricted to split \(( S_3, \ldots, S_p)\)-free graphs, where \(S_q\) denotes the \(q\)-sun graph.A fast algorithm for source-wise round-trip spannershttps://zbmath.org/1517.050702023-09-22T14:21:46.120933Z"Zhu, Chun Jiang"https://zbmath.org/authors/?q=ai:zhu.chun-jiang"Han, Song"https://zbmath.org/authors/?q=ai:han.song"Lam, Kam-Yiu"https://zbmath.org/authors/?q=ai:lam.kam-yiuSummary: In this paper, we study the problem of fast constructions of source-wise round-trip spanners in weighted directed graphs. For a source vertex set \(S \subseteq V\) in a graph \(G(V, E)\), an \(S\)-sourcewise round-trip spanner of \(G\) of stretch \(k\) is a subgraph \(H\) of \(G\) such that for every pair of vertices \(u, v \in S \times V\), their round-trip distance in \(H\) is at most \(k\) times of their round-trip distance in \(G\). We show that for a graph \(G(V, E)\) with \(n\) vertices and \(m\) edges, an \(s\)-sized source vertex set \(S \subseteq V\) and an integer \(k > 1\), there exists an algorithm that in time \(O(m s^{1 / k} \log^5 n)\) constructs an \(S\)-sourcewise round-trip spanner of stretch \(O(k \log n)\) and \(O(n s^{1 / k} \log^2 n)\) edges with high probability. Compared to the fast algorithms for constructing all-pairs round-trip spanners [\textit{J. Pachocki} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1374--1392 (2018; Zbl 1403.68173); \textit{S. Chechik} et al., in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22--26, 2020. New York, NY: Association for Computing Machinery (ACM). 1010--1023 (2020; Zbl 07298306)], our algorithm improves the running time and the number of edges in the spanner when \(k\) is super-constant. Compared with the existing algorithm for constructing source-wise round-trip spanners [\textit{C. J. Zhu} and \textit{K.-Y. Lam}, Inf. Process. Lett. 124, 42--45 (2017; Zbl 1416.05272)], our algorithm significantly improves their construction time \(\Omega(\min \{m s, n^\omega \})\) (where \(\omega \in [2, 2.373)\) and 2.373 is the matrix multiplication exponent) to nearly linear \(O(m s^{1 / k} \log^5 n)\), at the expense of paying an extra \(O(\log n)\) in the stretch. As an important building block of the algorithm, we develop a graph partitioning algorithm to partition \(G\) into clusters of bounded radius and prove that for every \(u, v \in S \times V\) at small round-trip distance, the probability of separating them in different clusters is small. The algorithm takes the size of \(S\) as input and does not need the knowledge of \(S\). With the algorithm and a reachability vertex size estimation algorithm, we show that the recursive algorithm for constructing standard round-trip spanners [Pachocki et al., loc. cit.] can be adapted to the source-wise setting. We rigorously prove the correctness and computational complexity of the adapted algorithms. Finally, we show how to remove the dependence on the edge weight in the source-wise case.Comparing the principal eigenvector of a hypergraph and its shadowshttps://zbmath.org/1517.050972023-09-22T14:21:46.120933Z"Clark, Gregory J."https://zbmath.org/authors/?q=ai:clark.gregory-j"Thomaz, Felipe"https://zbmath.org/authors/?q=ai:thomaz.felipe"Stephen, Andrew T."https://zbmath.org/authors/?q=ai:stephen.andrew-tSummary: Graphs (i.e., networks) have become an integral tool for the representation and analysis of relational data. Advances in data gathering have led to multi-relational data sets which exhibit greater depth and scope. In certain cases, this data can be modeled using a hypergraph. However, in practice analysts typically reduce the dimensionality of the data (whether consciously or otherwise) to accommodate a traditional graph model. In recent years spectral hypergraph theory has emerged to study the eigenpairs of the adjacency hypermatrix of a uniform hypergraph. We show how analyzing multi-relational data, via a hypermatrix associated to the aforementioned hypergraph, can lead to conclusions different from those when the data is projected down to its co-occurrence matrix. To this end we consider how the principal eigenvector of a hypergraph and its shadow can vary in terms of their spectral rankings, Pearson/Spearman correlation coefficient, and Chebyshev distance. In particular, we provide an example of a uniform hypergraph where the most central vertex (à la eigencentrality) changes depending on the order of the associated matrix. To the best of our knowledge this is the first known hypergraph to exhibit this property. We further show that the aforementioned eigenvectors have a high Pearson correlation but are uncorrelated under the Spearman correlation coefficient.Graphical designs and gale dualityhttps://zbmath.org/1517.051132023-09-22T14:21:46.120933Z"Babecki, Catherine"https://zbmath.org/authors/?q=ai:babecki.catherine"Thomas, Rekha R."https://zbmath.org/authors/?q=ai:thomas.rekha-rSummary: A graphical design is a subset of graph vertices such that the weighted averages of certain graph eigenvectors over the design agree with their global averages. We use Gale duality to show that positively weighted graphical designs in regular graphs are in bijection with the faces of a generalized eigenpolytope of the graph. This connection can be used to organize, compute and optimize designs. We illustrate the power of this tool on three families of Cayley graphs -- cocktail party graphs, cycles, and graphs of hypercubes -- by computing or bounding the smallest designs that average all but the last eigenspace in frequency order.On Petrie cycle and Petrie tour partitions of 3- and 4-regular plane graphshttps://zbmath.org/1517.051412023-09-22T14:21:46.120933Z"He, Xin"https://zbmath.org/authors/?q=ai:he.xin"Zhang, Huaming"https://zbmath.org/authors/?q=ai:zhang.huaming"Han, Yijie"https://zbmath.org/authors/?q=ai:han.yijieSummary: Given a plane graph \(G=(V,E)\), a Petrie tour of \(G\) is a tour \(P\) of \(G\) that alternately turns left and right at each step. A Petrie tour partition of \(G\) is a collection \({\mathscr P}=\{P_1, \ldots, P_q\}\) of Petrie tours so that each edge of \(G\) is in exactly one tour \(P_i \in{\mathscr P} \). A Petrie tour \(P\) is called a Petrie cycle if all its vertices are distinct. A Petrie cycle partition of \(G\) is a collection \({\mathscr C}=\{C_1, \ldots, C_p\}\) of Petrie cycles so that each vertex of \(G\) is in exactly one cycle \(C_i \in\mathscr{C}\). In this paper, we study the properties of 3-regular plane graphs that have Petrie cycle partitions and 4-regular plane multi-graphs that have Petrie tour partitions. Given a 4-regular plane multi-graph \(G=(V, E)\), a 3-regularization of \(G\) is a 3-regular plane graph \(G_3\) obtained from \(G\) by splitting every vertex \(v\in V\) into two degree-3 vertices. \(G\) is called Petrie partitionable if it has a 3-regularization that has a Petrie cycle partition. The general version of this problem is motivated by a data compression method, tristrip, used in computer graphics. In this paper, we present a simple characterization of Petrie partitionable graphs and show that the problem of determining if \(G\) is Petrie partitionable is NP-complete.Two-disjoint-cycle-cover vertex bipancyclicity of bipartite hypercube-like networkshttps://zbmath.org/1517.051452023-09-22T14:21:46.120933Z"Niu, Ruichao"https://zbmath.org/authors/?q=ai:niu.ruichao"Zhou, Shujie"https://zbmath.org/authors/?q=ai:zhou.shujie"Xu, Min"https://zbmath.org/authors/?q=ai:xu.minSummary: Let \(r_1\), \(r_2\) be two integers such that \(r_2 \geq r_1 \geq 0\). A bipartite graph \(G\) is two-disjoint-cycle-cover vertex \([ r_1, r_2]\)-bipancyclic (2-DCC vertex \([ r_1, r_2]\)-bipancyclic for short) if for any two vertices \(u, v \in V(G)\) and any even integer \(\ell\) satisfying \(r_1 \leq \ell \leq r_2\), there exist two vertex-disjoint cycles \(C_1\) and \(C_2\) in \(G\) with \(| V( C_1) | = \ell\) and \(| V( C_2) | = | V(G) | - \ell\) such that \(u \in V( C_1)\) and \(v \in V( C_2)\). In this paper, we study the 2-DCC vertex bipancyclicity of the \(n\)-dimensional bipartite hypercube-like network, which is one class of hypercube-generalized networks. As a consequence, we show that an \(n\)-dimensional bipartite hypercube-like network is 2-DCC vertex \([4, 2^{n - 1}]\)-bipancyclic for \(n \geq 3\). In particular, it provides an application that \(n\)-dimensional hypercube and bicube are also 2-DCC vertex \([4, 2^{n - 1}]\)-bipancyclic for \(n \geq 3\).On the minimum bisection of random 3-regular graphshttps://zbmath.org/1517.051602023-09-22T14:21:46.120933Z"Lichev, Lyuben"https://zbmath.org/authors/?q=ai:lichev.lyuben"Mitsche, Dieter"https://zbmath.org/authors/?q=ai:mitsche.dieterSummary: In this paper we give new bounds on the bisection width of random 3-regular graphs on \(n\) vertices. The main contribution is a new lower bound of \(0.103295n\) based on a first moment method together with a structural analysis of the graph, thereby improving a 27-year-old result of \textit{A. V. Kostochka} and \textit{L. S. Melnikov} [in: Вероятностные методы дискретной\ математики. Труды третьей\ Петрозаводской\ конференции. Петрозаводск (Россия), 11--16 мая 1992 г. Moskva: TVP; Utrecht: VSP. 251--265 (1993; Zbl 0811.05035)]. We also give a complementary upper bound of \(0.139822n\) by combining a result of Lyons with original combinatorial insights. Developping this approach further, we obtain a non-rigorous improved upper bound with the help of Monte Carlo simulations.Algorithms for the rainbow vertex coloring problem on graph classeshttps://zbmath.org/1517.051682023-09-22T14:21:46.120933Z"Lima, Paloma T."https://zbmath.org/authors/?q=ai:lima.paloma-t"van Leeuwen, Erik Jan"https://zbmath.org/authors/?q=ai:van-leeuwen.erik-jan"van der Wegen, Marieke"https://zbmath.org/authors/?q=ai:van-der-wegen.mariekeSummary: Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. In the Rainbow Vertex Coloring (RVC) problem we want to decide whether the vertices of a given graph can be colored with at most \(k\) colors so that the graph becomes rainbow vertex-connected. This problem is known to be NP-complete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomial-time algorithms for RVC on permutation graphs, powers of trees and split strongly chordal graphs. The algorithm for the latter class also works for the strong variant of the problem, where the rainbow vertex paths between each vertex pair must be shortest paths. We complement the polynomial-time solvability results for split strongly chordal graphs by showing that, for any fixed \(p\geq 3\) both variants of the problem become NP-complete when restricted to split \((S_3,\dots,S_p)\)-free graphs, where \(S_q\) denotes the \(q\)-sun graph.
For the entire collection see [Zbl 1445.68013].Combinatorial properties for a class of simplicial complexes extended from pseudo-fractal scale-free webhttps://zbmath.org/1517.051842023-09-22T14:21:46.120933Z"Xie, Zixuan"https://zbmath.org/authors/?q=ai:xie.zixuan"Wang, Yucheng"https://zbmath.org/authors/?q=ai:wang.yucheng"Xu, Wanyue"https://zbmath.org/authors/?q=ai:xu.wanyue"Zhu, Liwang"https://zbmath.org/authors/?q=ai:zhu.liwang"Li, Wei"https://zbmath.org/authors/?q=ai:li.wei.258"Zhang, Zhongzhi"https://zbmath.org/authors/?q=ai:zhang.zhongzhi(no abstract)\(\mathbb{Q}\)-bonacci words and numbershttps://zbmath.org/1517.110122023-09-22T14:21:46.120933Z"Kirgizov, Sergey"https://zbmath.org/authors/?q=ai:kirgizov.sergeySummary: We present a quite curious generalization of multi-step Fibonacci numbers. For any positive rational \(q\), we enumerate binary words of length \(n\) whose maximal factors of the form \(0^a1^b\) satisfy \(a=0\) or \(aq>b\). When \(q\) is an integer we rediscover classical multistep Fibonacci numbers: Fibonacci, Tribonacci, Tetranacci, etc. When \(q\) is not an integer, obtained recurrence relations are connected to certain restricted integer compositions. We also discuss Gray codes for these words, and a possibly novel generalization of the golden ratio.The \(p\)-Zassenhaus filtration of a free profinite group and shuffle relationshttps://zbmath.org/1517.120052023-09-22T14:21:46.120933Z"Efrat, Ido"https://zbmath.org/authors/?q=ai:efrat.idoLet \(G\) be a profinite group and \(p\) a prime number. The \(p\)-Zassenhaus filtration of \(G\) is given by the sequence \(G \sb {(n,p)}\), \(n \in \mathbb{N}\), where \(G \sb {(n,p)}\) is generated by all \(p \sp j\)-th powers of elements of the \(i\)-th term \(G \sp {(i)}\) of the profinite lower central filtration of \(G\), for \(ip \sp j \ge n\). Introduced by \textit{H. Zassenhaus} for discrete groups [Abh. Math. Semin. Univ. Hamb. 13, 200--207 (1939; Zbl 0021.20001)] as a tool to study free Lie algebras in characteristic \(p\), it has successfully been used in a number of group-theoretic and arithmetic problems: the Golod-Shafarevich solution to the class field tower problem [\textit{H. Koch}, Math. Nachr. 42, 321--333 (1969; Zbl 0191.33702)] Sect. 7.7 of [\textit{H. Koch}, Galois theory of \(p\)-extensions. Berlin: Springer (2002; Zbl 1023.11002); \textit{E. Zelmanov}, Prog. Math. 184, 223--232 (2000; Zbl 0974.20022); \textit{M. Ershov}, Int. J. Algebra Comput. 22, No. 5, Article ID 1230001, 68 p. (2012; Zbl 1286.20033)], the structure of finitely generated pro-\(p\)-groups of finite rank (see Ch. 11 of [\textit{J. D. Dixon} et al., Analytic pro-\(p\) groups. Revised and enlarged by Marcus du Sautoy and Dan Segal. 2nd ed. Cambridge: Cambridge University Press (1999; Zbl 0934.20001)], mild groups (see [\textit{J. Labute}, J. Reine Angew. Math. 596, 155--182 (2006; Zbl 1122.11076)] and one-relator pro-\(p\)-groups (Sect. 2.4 of [\textit{J. Gärtner}, Mild pro-\(p\)-groups with trivial cup-product. Heidelberg: Univ. Heidelberg, Naturwissenschaftlich-Mathematische Gesamtfakulät (Diss.). (2011; Zbl 1286.11203)], multiple residue symbols and their knot-theory analogues [\textit{M. Morishita}, Compos. Math. 140, No. 1, 69--83 (2004; Zbl 1066.11048)], and [\textit{D. Vogel}, J. Reine Angew. Math. 581, 117--150 (2005; Zbl 1143.11042)].
The purpose of the paper under review is to study the \(p\)-Zassenhaus filtration of a free pro-\(p\)-group \(S\) on a basis \(X\) and its cohomology by means of the combinatorics of words. Let Sh\((X) \sb {indec,n}\) be the \(n\)-th homogeneous component of the indecomposable quotient of the shuffle algebra Sh\((X)\), in the sense of the author's paper [\textit{I. Efrat}, J. Pure Appl. Algebra 224, No. 6, Article ID 106260, 13 p. (2020; Zbl 1506.20086)]. The main theorem of the reviewed paper states that if \(n < p\), then \(H \sp 2(S/S \sb {(n, p)}, \mathbb{Z}/p)\) is isomorphic as an \(\mathbb{F}\sb p\)-linear space to the direct sum \((\oplus \sb {x \in X} \mathbb{Z}/p) \oplus (Sh(X)\sb {indec,n} \otimes (\mathbb{Z}/p))\); also, the author finds a natural linear basis for this cohomology group, which is constructed by means of unitriangular representations arising from Lyndon words. When \(p \le n\), a similar result to the main theorem is obtained, in the form of a canonical epimorphism.
The reviewed paper builds upon earlier research of the author (see [\textit{I. Efrat}, Doc. Math. 22, 973--997 (2017; Zbl 1437.20047)], supplemented by his paper of 2020, noted above), where he proved analogous results for the lower \(p\)-central filtration, defined inductively by \(G \sp {(1, p)} = G\) and \(G \sp {(n,p)} = (G \sp {(n-1, p)}) \sp p.[G, G \sp {(n-1, p)}]\), for \(n \ge 2\). As explained in the text, this filtration and the \(p\)-Zassenhaus one are in many respects the opposite extremes among the filtrations related to mod-\(p\) cohomology. Thus it becomes possible to study the \(p\)-Zassenhaus filtration following the philosophy of the earlier papers; at the same time, it turns out to be necessary to modify their methods in several aspects presented to the reader.
Reviewer: Ivan D. Chipchakov (Sofia)Graph drawing and network visualization. 30th international symposium, GD 2022, Tokyo, Japan, September 13--16, 2022. Revised selected papershttps://zbmath.org/1517.680012023-09-22T14:21:46.120933ZThe articles of this volume will be reviewed individually. For the preceding symposium see [Zbl 1490.68027].
Indexed articles:
\textit{Suk, Andrew; Zeng, Ji}, Unavoidable patterns in complete simple topological graphs, 3-15 [Zbl 07727748]
\textit{Aichholzer, Oswin; Knorr, Kristin; Mulzer, Wolfgang; El Maalouly, Nicolas; Obenaus, Johannes; Paul, Rosna; Reddy, Meghana M.; Vogtenhuber, Birgit; Weinberger, Alexandra}, Compatible spanning trees in simple drawings of \(K_n\), 16-24 [Zbl 07727749]
\textit{Lenhart, William J.; Liotta, Giuseppe}, Mutual witness Gabriel drawings of complete bipartite graphs, 25-39 [Zbl 07727750]
\textit{García, Alfredo; Tejel, Javier; Vogtenhuber, Birgit; Weinberger, Alexandra}, Empty triangles in generalized twisted drawings of \(K_n\), 40-48 [Zbl 07727751]
\textit{Aichholzer, Oswin; García, Alfredo; Parada, Irene; Vogtenhuber, Birgit; Weinberger, Alexandra}, Shooting stars in simple drawings of \(K_{m,n}\), 49-57 [Zbl 07727752]
\textit{Giovannangeli, Loann; Lalanne, Frederic; Giot, Romain; Bourqui, Romain}, FORBID: Fast Overlap Removal By stochastic gradIent Descent for graph drawing, 61-76 [Zbl 07727753]
\textit{Miller, Jacob; Huroyan, Vahan; Kobourov, Stephen}, Spherical graph drawing by multi-dimensional scaling, 77-92 [Zbl 07727754]
\textit{Meidiana, Amyra; Hong, Seok-Hee; Eades, Peter}, Shape-faithful graph drawings, 93-108 [Zbl 07727755]
\textit{Cornelsen, Sabine; Diatzko, Gregor}, Planar confluent orthogonal drawings of 4-modal digraphs, 111-126 [Zbl 07727756]
\textit{Alegría, Carlos; Da Lozzo, Giordano; Di Battista, Giuseppe; Frati, Fabrizio; Grosso, Fabrizio; Patrignani, Maurizio}, Unit-length rectangular drawings of graphs, 127-143 [Zbl 07727757]
\textit{Bekos, Michael A.; Gronemann, Martin; Montecchiani, Fabrizio; Symvonis, Antonios}, Strictly-convex drawings of 3-connected planar graphs, 144-156 [Zbl 07727758]
\textit{Didimo, Walter; Kaufmann, Michael; Liotta, Giuseppe; Ortali, Giacomo}, Rectilinear planarity of partial 2-trees, 157-172 [Zbl 07727759]
\textit{Chaplick, Steven; Di Giacomo, Emilio; Frati, Fabrizio; Ganian, Robert; Raftopoulou, Chrysanthi N.; Simonov, Kirill}, Testing upward planarity of partial 2-trees, 175-187 [Zbl 07727760]
\textit{Geladaris, Vasileios; Lionakis, Panagiotis; Tollis, Ioannis G.}, Computing a feedback arc set using PageRank, 188-200 [Zbl 07727761]
\textit{Binucci, Carla; Didimo, Walter; Patrignani, Maurizio}, \(st\)-orientations with few transitive edges, 201-216 [Zbl 07727762]
\textit{Fox, Jacob; Pach, János; Suk, Andrew}, Quasiplanar graphs, string graphs, and the Erdős-Gallai problem, 219-231 [Zbl 07727763]
\textit{Nöllenburg, Martin; Sorge, Manuel; Terziadis, Soeren; Villedieu, Anaïs; Wu, Hsiang-Yun; Wulms, Jules}, Planarizing graphs and their drawings by vertex splitting, 232-246 [Zbl 07727764]
\textit{Cheong, Otfried; Pfister, Maximilian; Schlipf, Lena}, The thickness of fan-planar graphs is at most three, 247-260 [Zbl 07727765]
\textit{Ahmed, Reyan; Kobourov, Stephen; Kryven, Myroslav}, An FPT algorithm for bipartite vertex splitting, 261-268 [Zbl 07727766]
\textit{Filipov, Velitchko; Arleo, Alessio; Bögl, Markus; Miksch, Silvia}, On time and space: an experimental study on graph structural and temporal encodings, 271-288 [Zbl 07727767]
\textit{Di Battista, Giuseppe; Didimo, Walter; Grilli, Luca; Grosso, Fabrizio; Ortali, Giacomo; Patrignani, Maurizio; Tappini, Alessandra}, Small point-sets supporting graph stories, 289-303 [Zbl 07727768]
\textit{Binucci, Carla; Di Giacomo, Emilio; Lenhart, William J.; Liotta, Giuseppe; Montecchiani, Fabrizio; Nöllenburg, Martin; Symvonis, Antonios}, On the complexity of the storyplan problem, 304-318 [Zbl 07727769]
\textit{Gray, Kathryn; Li, Mingwei; Ahmed, Reyan; Kobourov, Stephen}, Visualizing evolving trees, 319-335 [Zbl 07727770]
\textit{Misue, Kazuo}, Improved scheduling of morphing edge drawing, 336-349 [Zbl 07727771]
\textit{Pupyrev, Sergey}, Queue layouts of two-dimensional posets, 353-360 [Zbl 07727772]
\textit{Bekos, Michael A.; Da Lozzo, Giordano; Frati, Fabrizio; Gronemann, Martin; Mchedlidze, Tamara; Raftopoulou, Chrysanthi N.}, Recognizing DAGs with page-number 2 is NP-complete, 361-370 [Zbl 07727773]
\textit{Bekos, Michael A.; Felsner, Stefan; Kindermann, Philipp; Kobourov, Stephen; Kratochvíl, Jan; Rutter, Ignaz}, The Rique-number of graphs, 371-386 [Zbl 07727774]
\textit{Chaplick, Steven; Kindermann, Philipp; Klawitter, Jonathan; Rutter, Ignaz; Wolff, Alexander}, Morphing rectangular duals, 389-403 [Zbl 07727775]
\textit{Biedl, Therese}, Visibility representations of toroidal and Klein-bottle graphs, 404-417 [Zbl 07727776]
\textit{Gutowski, Grzegorz; Mittelstädt, Florian; Rutter, Ignaz; Spoerhase, Joachim; Wolff, Alexander; Zink, Johannes}, Coloring mixed and directional interval graphs, 418-431 [Zbl 07727777]
\textit{Firman, Oksana; Kindermann, Philipp; Klawitter, Jonathan; Klemz, Boris; Klesen, Felix; Wolff, Alexander}, Outside-obstacle representations with all vertices on the outer face, 432-440 [Zbl 07727778]
\textit{Felsner, Stefan; Roch, Sandro; Scheucher, Manfred}, Arrangements of pseudocircles: on digons and triangles, 441-455 [Zbl 07727779]
\textit{Kindermann, Philipp; Klute, Fabian; Mchedlidze, Tamara; Meulemans, Wouter}, Graph drawing contest report, 459-470 [Zbl 07727780]SOFSEM 2023: theory and practice of computer science. 48th international conference on current trends in theory and practice of computer science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15--18, 2023. Proceedingshttps://zbmath.org/1517.680142023-09-22T14:21:46.120933ZThe articles of mathematical interest will be reviewed individually. For the preceding conference see [Zbl 1482.68014].26th international conference on theory and applications of satisfiability testing, SAT 2023, Alghero, Italy, July 4--8, 2023https://zbmath.org/1517.680232023-09-22T14:21:46.120933ZThe articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1494.68012].Locating number of biswapped networkshttps://zbmath.org/1517.680342023-09-22T14:21:46.120933Z"Nadeem, Muhammad Faisal"https://zbmath.org/authors/?q=ai:nadeem.muhammad-faisal"Ali, Waqar"https://zbmath.org/authors/?q=ai:ali.waqar"Siddiqui, Hafiz Muhammad Afzal"https://zbmath.org/authors/?q=ai:afzal-siddiqui.hafiz-muhammadSummary: A biswapped network is an interconnection network in multiprocessor systems. These are networks of devices or processors and connections of these devices or processors. Here network can be expressed in the form of a graph. Devices or processors represent vertices, and the connection of devices or processors represents edges. The subset of the nodes set is called the resolving set if all the representations or codes are different w.r.t. this subset gives the information about the complete network. The minimum cardinality of the resolving set is called the locating number. In this article, we find the locating number of biswapped interconnection networks. In this paper, We compute the exact values of locating numbers for biswapped networks generated by different families of underlying basis networks like path, cycle, power of path, and complete. We have also given the bounds of locating number of any biswapped network generated by any underlying basis network that consists of its clusters.Reducing polarization and increasing diverse navigability in graphs by inserting edges and swapping edge weightshttps://zbmath.org/1517.680372023-09-22T14:21:46.120933Z"Haddadan, Shahrzad"https://zbmath.org/authors/?q=ai:haddadan.shahrzad"Menghini, Cristina"https://zbmath.org/authors/?q=ai:menghini.cristina"Riondato, Matteo"https://zbmath.org/authors/?q=ai:riondato.matteo"Upfal, Eli"https://zbmath.org/authors/?q=ai:upfal.eliSummary: The sets of hyperlinks in web pages, relationship ties in social networks, or sets of recommendations in recommender systems, have a major impact on the diversity of content accessed by the user in a browsing session. Bias induced by the graph structure may trap a reader in a polarized bubble with no access to other opinions. It is widely accepted that exposure to diverse opinions creates more informed citizens and consumers. We introduce the concept of the \textit{polarized bubble radius} of a node, as the expected length of a random walk from it to a node of different opinion. Using the bubble radius, we define the measures of \textit{structural bias} and \textit{diverse navigability} to quantify the effect of links and recommendations on the diversity of content visited in a browsing session. We then propose algorithmic techniques to reduce the structural bias of the graph or improve the diverse navigability of the system through minimal modifications, such as edge insertions or flipping the order of existing links or recommendations, corresponding to switching the edge traversal probabilities. Under mild conditions, our techniques obtain a constant factor-approximation of their respective tasks. In our extensive experimental evaluation, we show that our algorithms reduce the structural bias or improve the diverse navigability faster than appropriate baselines, including some designed with the goal of reducing the polarization of a graph.Crash-tolerant consensus in directed graph revisited (extended abstract)https://zbmath.org/1517.680402023-09-22T14:21:46.120933Z"Choudhury, Ashish"https://zbmath.org/authors/?q=ai:choudhary.ashish"Garimella, Gayathri"https://zbmath.org/authors/?q=ai:garimella.gayathri"Patra, Arpita"https://zbmath.org/authors/?q=ai:patra.arpita"Ravi, Divya"https://zbmath.org/authors/?q=ai:ravi.divya"Sarkar, Pratik"https://zbmath.org/authors/?q=ai:sarkar.pratikSummary: Fault-tolerant distributed consensus is a fundamental problem in secure distributed computing. In this work, we consider the problem of distributed consensus in directed graphs tolerating crash failures. \textit{L. Tseng} and \textit{N. H. Vaidya} [PODC 2015, 451--460 (2015; Zbl 1333.68072)] presented necessary and sufficient condition for the existence of consensus protocols in directed graphs. We improve the round and communication complexity of their protocol. Moreover, we prove that our protocol requires the optimal number of communication rounds, required by any protocol belonging to a restricted class of crash-tolerant consensus protocols in directed graphs.
For the entire collection see [Zbl 1400.68027].A combinatorial characterization of self-stabilizing population protocolshttps://zbmath.org/1517.680482023-09-22T14:21:46.120933Z"Mathur, Shaan"https://zbmath.org/authors/?q=ai:mathur.shaan"Ostrovsky, Rafail"https://zbmath.org/authors/?q=ai:ostrovsky.rafail|ostrovsky.rafail-mSummary: We characterize self-stabilizing functions in population protocols for complete interaction graphs. In particular, we investigate self-stabilization in systems of \(n\) finite state agents in which a malicious scheduler selects an arbitrary sequence of pairwise interactions under a global fairness condition. We show a necessary and sufficient condition for self-stabilization. Specifically we show that functions without certain set-theoretic conditions are impossible to compute in a self-stabilizing manner. Our main contribution is in the converse, where we construct a self-stabilizing protocol for all other functions that meet this characterization. Our positive construction uses Dickson's Lemma to develop the notion of the root set, a concept that turns out to fundamentally characterize self-stabilization in this model. We believe it may lend to characterizing self-stabilization in more general models as well.
For the entire collection see [Zbl 1507.68029].Efficient dispersion of mobile agents without global knowledgehttps://zbmath.org/1517.680602023-09-22T14:21:46.120933Z"Shintaku, Takahiro"https://zbmath.org/authors/?q=ai:shintaku.takahiro"Sudo, Yuichi"https://zbmath.org/authors/?q=ai:sudo.yuichi"Kakugawa, Hirotsugu"https://zbmath.org/authors/?q=ai:kakugawa.hirotsugu"Masuzawa, Toshimitsu"https://zbmath.org/authors/?q=ai:masuzawa.toshimitsuSummary: We consider the dispersion problem for mobile agents. Initially, \(k\) agents are located at arbitrary nodes in an undirected graph. Agents can migrate from node to node via an edge in the graph synchronously. Our goal is to let the \(k\) agents be located at different \(k\) nodes while minimizing the number of steps before dispersion is completed and the working memory space used by the agents. \textit{A. D. Kshemkalyani} et al. [Lect. Notes Comput. Sci. 11931, 23--40 (2019; \url{doi:10.1007/978-3-030-34405-4_2}), contained in Zbl 1428.68015] present a fast and space-efficient dispersion algorithm with the assumption that each agent has global knowledge such as the number of edges and the maximum degree of a graph. In this paper, we present a dispersion algorithm that does not require such global knowledge but keeps the asymptotically same running time and slightly smaller memory space.
For the entire collection see [Zbl 1507.68029].Mixed fault tolerance in server assignment: combining reinforcement and backuphttps://zbmath.org/1517.680632023-09-22T14:21:46.120933Z"Navon, Tal"https://zbmath.org/authors/?q=ai:navon.tal"Peleg, David"https://zbmath.org/authors/?q=ai:peleg.davidSummary: We study the mixed approach to fault tolerance in the general context of server assignment in networks. The approach is based on mixing two different existing strategies, namely, reinforcement and backup. The former strategy protects clients by reinforcing the servers assigned to them and making them fault-resistant (at a possibly high cost), while the latter protects clients by assigning to them alternate low price backup servers that can replace their primary servers in case those fail. Applying the mixed approach to fault tolerance gives rise to new fault-tolerant variations of known server assignment problems. We introduce several NP-hard problems of this type, including the Mixed Fault-Tolerant Dominating set problem, the Mixed Fault-Tolerant Centers problem, and the Mixed Fault-Tolerant Facility Location problem, and present polynomial time approximation algorithms for them, demonstrating the viability of the mixed strategy for server assignment problems.
For the entire collection see [Zbl 1400.68027].Component conditional fault tolerance of hierarchical folded cubic networkshttps://zbmath.org/1517.680642023-09-22T14:21:46.120933Z"Sun, Xueli"https://zbmath.org/authors/?q=ai:sun.xueli"Fan, Jianxi"https://zbmath.org/authors/?q=ai:fan.jianxi"Cheng, Baolei"https://zbmath.org/authors/?q=ai:cheng.baolei"Liu, Zhao"https://zbmath.org/authors/?q=ai:liu.zhao.1|liu.zhao"Yu, Jia"https://zbmath.org/authors/?q=ai:yu.jiaSummary: For the sake of achieving higher reliability, conditional connectivity has gradually become well-known. Component connectivity, as a kind of conditional connectivity, is an extension of the classical connectivity. Given a simple and undirected graph \(G\) and a nonnegative integer \(r\), the \((r + 1)\)-component connectivity of graph \(G\), say \(c \kappa_{r + 1}(G)\), is the minimum number of a vertex cut whose removal causes the surviving graph to have at least \(r + 1\) components. Another basic parameter of reliability, diagnosability is often related to the number of components in the surviving graph. The \((r + 1)\)-component diagnosability, say \(c t_{r + 1}(G)\), is the maximum size of fault sets subject to at least \(r + 1\) components in the surviving graph, provided that all faulty vertices can be detected. A graph is \(t / k\)-diagnosable if all faulty vertices can be isolated into a set in which up to \(k\) vertices are fault-free, provided that the number of faulty vertices is at most \(t\). As a two-level interconnection network, the hierarchical folded cubic network \(H F Q(n)\) possesses a great deal of nice properties. In this paper, we first show that the \(n\)-dimensional hierarchical folded cubic network is tightly super connected. Then, we explore that \(c \kappa_{r + 1}(H F Q(n)) = r(n + 1) - \binom {r} {2} + 1\) (\(n \geq 4\), \(1 \leq r \leq n - 4\)), and obtain that \(c t_{r + 1}(H F Q(n)) = (r + 1) n - \binom {r} {2} + 2\) (\(n \geq 4\), \(1 \leq r \leq n - 4\)) under the PMC and MM* models. Last, we show that the hierarchical folded cubic network \(H F Q(n)\) is \([(k + 1) n - \binom {k} {2} + 2] / k\)-diagnosable, where \(n \geq 4\) and \(1 \leq k \leq n - 4\).Truncated DAWGs and their application to minimal absent word problemhttps://zbmath.org/1517.680902023-09-22T14:21:46.120933Z"Fujishige, Yuta"https://zbmath.org/authors/?q=ai:fujishige.yuta"Takagi, Takuya"https://zbmath.org/authors/?q=ai:takagi.takuya"Hendrian, Diptarama"https://zbmath.org/authors/?q=ai:hendrian.diptaramaSummary: The \textit{directed acyclic word graph} (\textit{DAWG}) of a string \(y\) is the smallest (partial) DFA which recognizes all suffixes of \(y\) and has \(O(n)\) nodes and edges. \textit{J. C. Na} et al. [Theor. Comput. Sci. 304, No. 1--3, 87--101 (2003; Zbl 1044.68031)] proposed \(k\)-truncated suffix tree which is a compressed trie that represents substrings of a string whose length up to \(k\). In this paper, we present a new data structure called \(k\)-\textit{truncated DAWGs}, which can be obtained by pruning the DAWGs. We show that the size complexity of the \(k\)-truncated DAWG of a string \(y\) of length \(n\) is \(O(\min \{n,kz\})\) which is equal to the truncated suffix tree's one, where \(z\) is the size of LZ77 factorization of \(y\). We also present an \(O(n\log \sigma )\) time and \(O(\min \{ n,kz\})\) space algorithm for constructing the \(k\)-truncated DAWG of \(y\), where \(\sigma\) is the alphabet size. As an application of the truncated DAWGs, we show that the set \(\operatorname{MAW}_k(y)\) of all minimal absent words of \(y\) whose length is smaller than or equal to \(k\) can be computed by using \(k\)-truncated DAWG of \(y\) in \(O(\min \{ n, kz\} + |\operatorname{MAW}_k(y)|)\) time and \(O(\min \{ n,kz\})\) working space.
For the entire collection see [Zbl 1398.68028].On Tseitin formulas, read-once branching programs and treewidthhttps://zbmath.org/1517.680912023-09-22T14:21:46.120933Z"Glinskih, Ludmila"https://zbmath.org/authors/?q=ai:glinskih.ludmila"Itsykson, Dmitry"https://zbmath.org/authors/?q=ai:itsykson.dmitry-mSummary: We show that any nondeterministic read-once branching program that decides a satisfiable Tseitin formula based on an \(n\times n\) grid graph has size at least \(2^{\varOmega (n)}\). Then using the Excluded Grid theorem by Robertson and Seymour we show that for arbitrary graph \(G(V, E)\) any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on \(G\) has size at least \(2^{\varOmega (\operatorname{tw}(G)^\delta )}\) for all \(\delta <1/36\), where \(\operatorname{tw}(G)\) is the treewidth of \(G\) (for planar graphs and some other classes of graphs the statement holds for \(\delta =1)\). We also show an upper bound of \(O(|E| 2^{\operatorname{pw}(G)})\), where \(\operatorname{pw}(G)\) is the pathwidth of \(G\).
We apply the mentioned results to the analysis of the complexity of derivations in the proof system \(\mathrm{OBDD}(\land, \mathrm{reordering})\) and show that any \(\mathrm{OBDD}(\land, \mathrm{reordering})\)-refutation of an unsatisfiable Tseitin formula based on a graph \(G\) has size at least \(2^{\varOmega (\operatorname{tw}(G)^\delta )}\).
For the entire collection see [Zbl 1416.68013].On Tseitin formulas, read-once branching programs and treewidthhttps://zbmath.org/1517.680922023-09-22T14:21:46.120933Z"Glinskih, Ludmila"https://zbmath.org/authors/?q=ai:glinskih.ludmila"Itsykson, Dmitry"https://zbmath.org/authors/?q=ai:itsykson.dmitry-mSummary: We show that any nondeterministic read-once branching program that decides a satisfiable Tseitin formula based on an \(n\times n\) grid graph has size at least \(2^{ \Omega (n)}\). Then using the Excluded Grid Theorem by Robertson and Seymour we show that for an arbitrary graph \(G(V,E)\) any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on \(G\) has size at least \(2^{\Omega (\operatorname{tw}(G)^{\delta})}\) for all \(\delta<1/36\), where \(\operatorname{tw}(G)\) is the treewidth of \(G\) (for planar graphs and some other classes of graphs the statement holds for \(\delta = 1)\). We apply the mentioned results to the analysis of the complexity of derivations in the proof system \(\mathrm{OBDD}(\land, \mathrm{reordering})\) and show that any \(\mathrm{OBDD}(\land, \mathrm{reordering})\)-refutation of an unsatisfiable Tseitin formula based on a graph \(G\) has size at least \(2^{\Omega(\operatorname{tw}(G)^{\delta})}\). We also show an upper bound \(O(|E|2^{\operatorname{pw}(G)} )\) on the size of OBDD representations of a satisfiable Tseitin formula based on \(G\) and an upper bound \(O(|E||V| 2^{\operatorname{pw}(G)}+|\mathrm{TS}_{G,c}|^2)\) on the size of \(\mathrm{OBDD}(\land)\)-refutation of an unsatisifable Tseitin formula \(\mathrm{TS}_{G,c}\), where \(\operatorname{pw}(G)\) is the pathwidth of \(G\).The power of distributed verifiers in interactive proofshttps://zbmath.org/1517.681342023-09-22T14:21:46.120933Z"Naor, Moni"https://zbmath.org/authors/?q=ai:naor.moni"Parter, Merav"https://zbmath.org/authors/?q=ai:parter.merav"Yogev, Eylon"https://zbmath.org/authors/?q=ai:yogev.eylonCommunication complexity in vertex partition whiteboard modelhttps://zbmath.org/1517.681372023-09-22T14:21:46.120933Z"Jurdzinski, Tomasz"https://zbmath.org/authors/?q=ai:jurdzinski.tomasz"Lorys, Krzysztof"https://zbmath.org/authors/?q=ai:lorys.krzysztof"Nowicki, Krzysztof"https://zbmath.org/authors/?q=ai:nowicki.krzysztofSummary: We study the multi-party communication model, where players correspond to the nodes of a graph and each player knows its neighbors in the input graph. The players can send messages on a whiteboard which are immediately available to each player. Eventually, the referee which knows only messages on the whiteboard is supposed to give a solution to the considered (graph) problem. We distinguish between oblivious and adaptive variant of the model. The former model is related to simultaneous multi-party communication complexity, while the latter is closely related to so-called broadcast congested clique.
Communication complexity is the maximum over all nodes of the sizes of messages put on the whiteboard by a node. Our goal is to study the impact of adaptivity on communication complexity of graph problems. We show that there exists an infinite hierarchy of problems with respect to the number of rounds for constant size messages. Moreover, motivated by unsuccessful attempts to establish non-adaptive communication complexity of graph connectivity in recent years, we study the connectivity problem in the severely restricted class of two-regular graphs. We determine an asymptotically tight bound on communication complexity in the oblivious model and provide \(\omega(1)\) lower bound on the number of rounds in the adaptive model for some message size \(b(n)=\omega(1)\).
For the entire collection see [Zbl 1400.68027].Parameterized complexity of conflict-free set coverhttps://zbmath.org/1517.681452023-09-22T14:21:46.120933Z"Jacob, Ashwin"https://zbmath.org/authors/?q=ai:jacob.ashwin"Majumdar, Diptapriyo"https://zbmath.org/authors/?q=ai:majumdar.diptapriyo"Raman, Venkatesh"https://zbmath.org/authors/?q=ai:raman.venkateshSummary: Set Cover is one of the well-known classical NP-hard problems. Following some recent trends, we study the conflict-free version of the Set Cover problem. Here we have a universe \({\mathcal U}\), a family \({\mathcal F}\) of subsets of \({\mathcal U}\) and a graph \(G_{{\mathcal F}}\) on the vertex set \({\mathcal F}\) and we look for a subfamily \({\mathcal F}' \subseteq{\mathcal F}\) of minimum size that covers \({\mathcal U}\) and also forms an independent set in \(G_{{\mathcal F}}\). Here we initiate a systematic study of the problem in parameterized complexity by restricting the focus to the variants where Set Cover is fixed-parameter tractable (FPT). We give upper bounds and lower bounds for conflict-free version of the Set Cover with and without duplicate sets along with restrictions to the graph classes of \(G_{{\mathcal F}}\).
For the entire collection see [Zbl 1416.68013].Parameterized complexity of conflict-free set coverhttps://zbmath.org/1517.681462023-09-22T14:21:46.120933Z"Jacob, Ashwin"https://zbmath.org/authors/?q=ai:jacob.ashwin"Majumdar, Diptapriyo"https://zbmath.org/authors/?q=ai:majumdar.diptapriyo"Raman, Venkatesh"https://zbmath.org/authors/?q=ai:raman.venkateshSummary: \textsc{Set Cover} is one of the well-known classical NP-hard problems. We study the \textit{conflict-free} version of the \textsc{Set Cover} problem. Here we have a universe \(\mathcal{U}\), a family \(\mathcal{F}\) of subsets of \(\mathcal{U}\) and a graph \(G_{\mathcal{F}}\) on the vertex set \(\mathcal{F}\) and we look for a subfamily \(\mathcal{F}'\subseteq\mathcal{F}\) of minimum size that covers \(\mathcal{U}\) and also forms an independent set in \(G_{\mathcal{F}}\). We study conflict-free \textsc{Set Cover} in parameterized complexity by restricting the focus to the variants where \textsc{Set Cover} is fixed parameter tractable (FPT). We give upper bounds and lower bounds for the running time of conflict-free version of \textsc{Set Cover} with and without duplicate sets along with restrictions to the graph classes of \(G_{\mathcal{F}}\). For example, when pairs of sets in \(\mathcal{F}\) intersect in at most one element, for a solution of size \(k\), we give
\begin{itemize}
\item an \(f(k)|\mathcal{F}|^{o(k)}\) lower bound for any computable function \(f\) assuming ETH even if \(G_{\mathcal{F}}\) is bipartite, but
\item an \(O^*(3^{k^2})\) FPT algorithm \((\mathcal{O}^*\) notation ignores polynomial factors of input) when \(G_{\mathcal{F}}\) is chordal.
\end{itemize}Minimal automaton for multiplying and translating the Thue-Morse sethttps://zbmath.org/1517.681792023-09-22T14:21:46.120933Z"Charlier, Émilie"https://zbmath.org/authors/?q=ai:charlier.emilie"Cisternino, Célia"https://zbmath.org/authors/?q=ai:cisternino.celia"Massuir, Adeline"https://zbmath.org/authors/?q=ai:massuir.adelineSummary: The Thue-Morse set \(\mathcal{T}\) is the set of those non-negative integers whose binary expansions have an even number of \(1\)'s. The name of this set comes from the fact that its characteristic sequence is given by the famous Thue-Morse word \[\mathtt{0110100110010110}\cdots,\] which is the fixed point starting with \(0\) of the word morphism \(\mathtt{0\mapsto 01}\), \(\mathtt{1\mapsto 10}\). The numbers in \(\mathcal{T}\) are commonly called the evil numbers. We obtain an exact formula for the state complexity of the set \(m\mathcal{T}+r\) (i.e. the number of states of its minimal automaton) with respect to any base \(b\) which is a power of \(2\). Our proof is constructive and we are able to explicitly provide the minimal automaton of the language of all \(2^p\)-expansions of the set of integers \(m\mathcal{T}+r\) for any positive integers \(p\) and \(m\) and any remainder \(r\in\{0,\ldots,m{-}1\} \). The proposed method is general for any \(b\)-recognizable set of integers.Automata, palindromes, and reversed subwordshttps://zbmath.org/1517.681872023-09-22T14:21:46.120933Z"Fleischer, Lukas"https://zbmath.org/authors/?q=ai:fleischer.lukas"Shallit, Jeffrey"https://zbmath.org/authors/?q=ai:shallit.jeffrey-oSummary: In [Theor. Comput. Sci. 481, 1--8 (2013; Zbl 1291.68307)], \textit{G. Fici} and \textit{L. Q. Zamboni} proved a number of theorems about finite and infinite words having only a small number of factors that are palindromes. Earlier, in [J. Comb. Math. Comb. Comput. 54, 157--164 (2005; Zbl 1081.68076)], \textit{N. Rampersad} and the second author had proved a number of theorems about infinite words \(\mathbf{x}\) with the property that if \(w\) is any sufficiently long finite factor of \(\mathbf{x}\), then its reversal \(w^R\) is \textit{not} a factor of \(\mathbf{x}\). In both cases, the arguments used were typically case-based and somewhat involved.
In this note we rederive most of these results, and obtain many new ones, by a different method based on finite automata. Two variations of the method are presented. One advantage to our method is that it replaces complicated case-based proofs with (relatively simple) machine computations. Another advantage is that our method can provide detailed enumeration results about the number of words satisfying the various conditions. We explore these ideas in detail.Exhaustive generation of some lattice paths and their prefixeshttps://zbmath.org/1517.682642023-09-22T14:21:46.120933Z"Barcucci, Elena"https://zbmath.org/authors/?q=ai:barcucci.elena"Bernini, Antonio"https://zbmath.org/authors/?q=ai:bernini.antonio"Pinzani, Renzo"https://zbmath.org/authors/?q=ai:pinzani.renzoSummary: We refer to positive lattice paths as to paths in the discrete plane constituted by different kinds of steps (north-east, east and south-east), starting from the origin and never going under the \(x\)-axis. They have been deeply studied both from a combinatorial and an algorithmic point of view. We propose some algorithms for the exhaustive generation of positive paths which are Motzkin and Schröder paths and their prefixes, according to their length. For each kind of paths we define a recursive algorithm as well as an iterative one, specifying which path follows a given one in the lexicographic order. Furthermore we study the complexity of these algorithms by using the relations between the number of paths of a given size and the number of final north-east or south-east steps.Recursive online enumeration of all minimal unsatisfiable subsetshttps://zbmath.org/1517.682652023-09-22T14:21:46.120933Z"Bendík, Jaroslav"https://zbmath.org/authors/?q=ai:bendik.jaroslav"Černá, Ivana"https://zbmath.org/authors/?q=ai:cerna.ivana"Beneš, Nikola"https://zbmath.org/authors/?q=ai:benes.nikolaSummary: In various areas of computer science, we deal with a set of constraints to be satisfied. If the constraints cannot be satisfied simultaneously, it is desirable to identify the core problems among them. Such cores are called minimal unsatisfiable subsets (MUSes). The more MUSes are identified, the more information about the conflicts among the constraints is obtained. However, a full enumeration of all MUSes is in general intractable due to the large number (even exponential) of possible conflicts. Moreover, to identify MUSes, algorithms have to test sets of constraints for their simultaneous satisfiability. The type of the test depends on the application domains. The complexity of the tests can be extremely high especially for domains like temporal logics, model checking, or SMT. In this paper, we propose a recursive algorithm that identifies MUSes in an \textit{online} manner (i.e., one by one) and can be terminated at any time. The key feature of our algorithm is that it minimises the number of satisfiability tests and thus speeds up the computation. The algorithm is applicable to an arbitrary constraint domain. We benchmark our algorithm against the state-of-the-art algorithm Marco on the Boolean and SMT constraint domains and demonstrate that our algorithm really requires less satisfiability tests and consequently finds more MUSes in the given time limits.
For the entire collection see [Zbl 1396.68018].Reformulation of SAT into a polynomial box-constrained optimization problemhttps://zbmath.org/1517.682662023-09-22T14:21:46.120933Z"Jacquet, Stéphane"https://zbmath.org/authors/?q=ai:jacquet.stephane"Hallé, Sylvain"https://zbmath.org/authors/?q=ai:halle.sylvainSummary: In order to leverage the capacities of non-linear constraint solvers, we propose a reformulation of SAT into a box-constrained optimization problem where the objective function is polynomial. We prove that any optimal solution of the numerical problem corresponds to a solution of the Boolean formula, and demonstrate a stopping criterion that can be used with a numerical solver.
For the entire collection see [Zbl 1507.68030].New and improved algorithms for unordered tree inclusionhttps://zbmath.org/1517.682672023-09-22T14:21:46.120933Z"Akutsu, Tatsuya"https://zbmath.org/authors/?q=ai:akutsu.tatsuya"Jansson, Jesper"https://zbmath.org/authors/?q=ai:jansson.jesper"Li, Ruiming"https://zbmath.org/authors/?q=ai:li.ruiming"Takasu, Atsuhiro"https://zbmath.org/authors/?q=ai:takasu.atsuhiro"Tamura, Takeyuki"https://zbmath.org/authors/?q=ai:tamura.takeyukiSummary: The \textit{tree inclusion problem} is, given two node-labeled trees \(P\) and \(T\) (the ``pattern tree'' and the ``target tree''), to locate every minimal subtree in \(T\) (if any) that can be obtained by applying a sequence of node insertion operations to \(P\). Although the \textit{ordered} tree inclusion problem is solvable in polynomial time, the \textit{unordered} tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is a classic algorithm by Kilpeläinen and Mannila from 1995 that runs in \(O(d 2^{2 d} m n)\) time, where \(m\) and \(n\) are the sizes of the pattern and target trees, respectively, and \(d\) is the degree of the pattern tree. Here, we develop a new algorithm that runs in \(O(d 2^d m n^2)\) time, improving the exponential factor from \(2^{2 d}\) to \(2^d\) by considering a particular type of ancestor-descendant relationships that is suitable for dynamic programming. We also study restricted variants of the unordered tree inclusion problem.New and improved algorithms for unordered tree inclusionhttps://zbmath.org/1517.682682023-09-22T14:21:46.120933Z"Akutsu, Tatsuya"https://zbmath.org/authors/?q=ai:akutsu.tatsuya"Jansson, Jesper"https://zbmath.org/authors/?q=ai:jansson.jesper"Li, Ruiming"https://zbmath.org/authors/?q=ai:li.ruiming"Takasu, Atsuhiro"https://zbmath.org/authors/?q=ai:takasu.atsuhiro"Tamura, Takeyuki"https://zbmath.org/authors/?q=ai:tamura.takeyukiSummary: The tree inclusion problem is, given two node-labeled trees \(P\) and \(T\) (the ``pattern tree'' and the ``text tree''), to locate every minimal subtree in \(T\) (if any) that can be obtained by applying a sequence of node insertion operations to \(P\). Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is from 1995 and runs in \(O(\operatorname{poly}(m,n)\cdot 2^{2d})= O^*(2^{2d})\) time, where \(m\) and \(n\) are the sizes of the pattern and text trees, respectively, and \(d\) is the maximum outdegree of the pattern tree. Here, we develop a new algorithm that improves the exponent \(2d\) to \(d\) by considering a particular type of ancestor-descendant relationships and applying dynamic programming, thus reducing the time complexity to \(O^*(2^d)\). We then study restricted variants of the unordered tree inclusion problem where the number of occurrences of different node labels and/or the input trees' heights are bounded. We show that although the problem remains NP-hard in many such cases, it can be solved in polynomial time for \(c=2\) and in \(O^*(1.8^d)\) time for \(c=3\) if the leaves of \(P\) are distinctly labeled and each label occurs at most \(c\) times in \(T\). We also present a randomized \(O^*(1.883^d)\)-time algorithm for the case that the heights of \(P\) and \(T\) are one and two, respectively.
For the entire collection see [Zbl 1407.68036].Recoloring the colored de Bruijn graphhttps://zbmath.org/1517.682692023-09-22T14:21:46.120933Z"Alipanahi, Bahar"https://zbmath.org/authors/?q=ai:alipanahi.bahar"Kuhnle, Alan"https://zbmath.org/authors/?q=ai:kuhnle.alan"Boucher, Christina"https://zbmath.org/authors/?q=ai:boucher.christinaSummary: The colored de Bruijn graph, an extension of the de Bruijn graph, is routinely applied for variant calling, genotyping, genome assembly, and various other applications. In this data structure, the edges are labeled with one or more colors from a set \(\{c_1, \dots , c_{\alpha } \}\), and are stored as a \(m \times \alpha\) matrix, where \(m\) is the number of edges. Recently, there has been a significant amount of work in developing compacted representations of this color matrix but all existing methods have focused on compressing the color matrix. In this paper, we explore the problem of recoloring the graph in order to reduce the number of colors, and thus, decrease the size of the color matrix. We show that finding the minimum number of colors needed for recoloring is not only NP-hard but also, difficult to approximate within a reasonable factor. These hardness results motivate the need for a recoloring heuristic that we present in this paper. Our results show that this heuristic is able to reduce the number of colors between one and two orders of magnitude. More specifically, when the number of colors is large (>5,000,000) the number of colors is reduced by a factor of 136 by our heuristic. An implementation of this heuristic is publicly available at \url{https://github.com/baharpan/cosmo/tree/Recoloring}.
For the entire collection see [Zbl 1398.68028].Finding cores of limited lengthhttps://zbmath.org/1517.682702023-09-22T14:21:46.120933Z"Alstrup, Stephen"https://zbmath.org/authors/?q=ai:alstrup.stephen"Lauridsen, Peter W."https://zbmath.org/authors/?q=ai:lauridsen.peter-w"Sommerlund, Peer"https://zbmath.org/authors/?q=ai:sommerlund.peer"Thorup, Mikkel"https://zbmath.org/authors/?q=ai:thorup.mikkelSummary: In this paper we consider the problem of finding a core of limited length in a tree. A core is a path, which minimizes the sum of the distances to all nodes in the tree. This problem has been examined under different constraints on the tree and on the set of paths, from which the core can be chosen. For all cases, we present linear or almost linear time algorithms, which improves the previous results due to
[\textit{S. Peng} and \textit{W.-t. Lo}, J. Algorithms 20, No. 3, 445--458 (1996; Zbl 0845.68053); \textit{E. Minieka}, Networks 15, 309--321 (1985; Zbl 0579.90027)].
For the entire collection see [Zbl 1492.68014].Realizability of graph specifications: characterizations and algorithmshttps://zbmath.org/1517.682712023-09-22T14:21:46.120933Z"Bar-Noy, Amotz"https://zbmath.org/authors/?q=ai:bar-noy.amotz"Choudhary, Keerti"https://zbmath.org/authors/?q=ai:choudhary.keerti"Peleg, David"https://zbmath.org/authors/?q=ai:peleg.david"Rawitz, Dror"https://zbmath.org/authors/?q=ai:rawitz.drorSummary: The study of graphs and networks often involves studying various parameters of the graph vertices, capturing different aspects of the graph structure, such as the vertex degrees or the distances between the vertices. Given an \(n\)-vertex graph \(G\) and a parameter of interest \(f\), one may associate with \(G\) a vector \(\mathcal{F}(G)=\langle f_1,\ldots,f_n\rangle\) giving the value of \(f\) for each vertex. This vector can be thought of as the \(f\)-profile of the graph. This paper concerns the dual problem, where given an \(n\)-entry \(f\)-specification vector \(F=\langle f_1,\ldots,f_n\rangle\), we need to decide whether it is possible to find a graph \(G\) realizing this specification, namely, whose \(f\)-profile \(\mathcal{F}(G)\) conforms to \(F\). The paper introduces the notion of graph realiziations and illustrates a number of example problems related to finding graph realiziations for given specifications.
For the entire collection see [Zbl 1400.68027].On minimum connecting transition sets in graphshttps://zbmath.org/1517.682722023-09-22T14:21:46.120933Z"Bellitto, Thomas"https://zbmath.org/authors/?q=ai:bellitto.thomas"Bergougnoux, Benjamin"https://zbmath.org/authors/?q=ai:bergougnoux.benjaminSummary: A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the graph. In this paper, we look for the smallest set of transitions needed to be able to go from any vertex of the given graph to any other. We prove that this problem is NP-hard and study approximation algorithms. We develop theoretical tools that help to study this problem.
For the entire collection see [Zbl 1398.68016].Token sliding on split graphshttps://zbmath.org/1517.682732023-09-22T14:21:46.120933Z"Belmonte, Rémy"https://zbmath.org/authors/?q=ai:belmonte.remy"Kim, Eun Jung"https://zbmath.org/authors/?q=ai:kim.eun-jung"Lampis, Michael"https://zbmath.org/authors/?q=ai:lampis.michael"Mitsou, Valia"https://zbmath.org/authors/?q=ai:mitsou.valia"Otachi, Yota"https://zbmath.org/authors/?q=ai:otachi.yota"Sikora, Florian"https://zbmath.org/authors/?q=ai:sikora.florianSummary: We consider the complexity of the \textsc{Independent Set Reconfiguration} problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the \(c\)-\textsc{Colorable Reconfiguration} problem under the same rule, where the constraint is now to maintain the set \(c\)-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed \(c\geq 1\) on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time \((n^{O(c)})\) algorithm for all fixed values of \(c\), except \(c=1\), for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that \(c\)-\textsc{Colorable Reconfiguration} is W[2]-hard on split graphs parameterized by \(c\) and the length of the solution, as well as a tight ETH-based lower bound for both parameters. Finally, we study \(c\)-\textsc{Colorable Reconfiguration} under a relaxed rule called Token Jumping, where exchanged vertices are not required to be adjacent. We show that the problem on chordal graphs is PSPACE-complete even if \(c\) is some fixed constant. We then show that the problem is polynomial-time solvable for strongly chordal graphs even if \(c\) is a part of the input.Token sliding on split graphshttps://zbmath.org/1517.682742023-09-22T14:21:46.120933Z"Belmonte, Rémy"https://zbmath.org/authors/?q=ai:belmonte.remy"Kim, Eun Jung"https://zbmath.org/authors/?q=ai:kim.eun-jung"Lampis, Michael"https://zbmath.org/authors/?q=ai:lampis.michael"Mitsou, Valia"https://zbmath.org/authors/?q=ai:mitsou.valia"Otachi, Yota"https://zbmath.org/authors/?q=ai:otachi.yota"Sikora, Florian"https://zbmath.org/authors/?q=ai:sikora.florianSummary: We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area.\par We then go on to consider the \(c\)-Colorable Reconfiguration problem under the same rule, where the constraint is now to maintain the set \(c\)-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed \(c\ge 1\) on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time \((n^{O(c)})\) algorithm for all fixed values of \(c\), except \(c=1\), for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that \(c\)-Colorable Reconfiguration is W[2]-hard on split graphs parameterized by \(c\) and the length of the solution, as well as a tight ETH-based lower bound for both parameters.
For the entire collection see [Zbl 1411.68018].A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) roundshttps://zbmath.org/1517.682752023-09-22T14:21:46.120933Z"Ben-Basat, Ran"https://zbmath.org/authors/?q=ai:ben-basat.ran"Even, Guy"https://zbmath.org/authors/?q=ai:even.guy"Kawarabayashi, Ken-ichi"https://zbmath.org/authors/?q=ai:kawarabayashi.ken-ichi"Schwartzman, Gregory"https://zbmath.org/authors/?q=ai:schwartzman.gregorySummary: We present a deterministic distributed 2-approximation algorithm for the Minimum Weight Vertex Cover problem in the CONGEST model whose round complexity is \(O(\log n\log\varDelta/\log ^2\log\varDelta)\). This improves over the currently best known deterministic 2-approximation implied by [\textit{S. Khuller} et al., J. Algorithms 17, No. 2, 280--289 (1994; Zbl 0938.68946)]. Our solution generalizes the \((2+\epsilon)\)-approximation algorithm of [\textit{R. Bar-Yehuda} et al., J. ACM 64, No. 3, Article No. 23, 11 p. (2017; Zbl 1426.68291)], improving the dependency on \(\epsilon^{-1}\) from linear to logarithmic. In addition, for every \(\epsilon=(\log\varDelta)^{-c}\), where \(c\geq 1\) is a constant, our algorithm computes a \(\left(2+\epsilon\right)\)-approximation in \(O(\log{\varDelta}/\log\log{\varDelta})\) rounds (which is asymptotically optimal).
For the entire collection see [Zbl 1400.68027].Recognizing hyperelliptic graphs in polynomial timehttps://zbmath.org/1517.682762023-09-22T14:21:46.120933Z"Bodewes, Jelco M."https://zbmath.org/authors/?q=ai:bodewes.jelco-m"Bodlaender, Hans L."https://zbmath.org/authors/?q=ai:bodlaender.hans-l"Cornelissen, Gunther"https://zbmath.org/authors/?q=ai:cornelissen.gunther"van der Wegen, Marieke"https://zbmath.org/authors/?q=ai:van-der-wegen.mariekeSummary: Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time \(O(n\log n+m)\), where \(n\) is the number of vertices and \(m\) the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph \(G\) admits an involution \(\sigma\) such that the quotient \(G/\langle\sigma\rangle\) is a tree.
For the entire collection see [Zbl 1398.68016].On directed feedback vertex set parameterized by treewidthhttps://zbmath.org/1517.682772023-09-22T14:21:46.120933Z"Bonamy, Marthe"https://zbmath.org/authors/?q=ai:bonamy.marthe"Kowalik, Łukasz"https://zbmath.org/authors/?q=ai:kowalik.lukasz"Nederlof, Jesper"https://zbmath.org/authors/?q=ai:nederlof.jesper"Pilipczuk, Michał"https://zbmath.org/authors/?q=ai:pilipczuk.michal"Socała, Arkadiusz"https://zbmath.org/authors/?q=ai:socala.arkadiusz"Wrochna, Marcin"https://zbmath.org/authors/?q=ai:wrochna.marcinSummary: We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot be solved in time \(2^{o(t\log t)}\cdot n^{\mathcal{O}(1)}\) on general directed graphs, where \(t\) is the treewidth of the underlying undirected graph. This is matched by a dynamic programming algorithm with running time \(2^{\mathcal{O}(t\log t)}\cdot n^{\mathcal {O}(1)}\). On the other hand, we show that if the input digraph is planar, then the running time can be improved to \(2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}\).
For the entire collection see [Zbl 1398.68016].Optimality program in segment and string graphshttps://zbmath.org/1517.682782023-09-22T14:21:46.120933Z"Bonnet, Édouard"https://zbmath.org/authors/?q=ai:bonnet.edouard"Rzążewski, Paweł"https://zbmath.org/authors/?q=ai:rzazewski.pawelSummary: Planar graphs are known to allow subexponential algorithms running in time \(2^{O(\sqrt{n})}\) or \(2^{O(\sqrt{n}\log n)}\) for most of the paradigmatic problems, while the brute-force time \(2^{\varTheta(n)}\) is very likely to be asymptotically best on general graphs. Intrigued by an algorithm packing curves in \(2^{O(n^{2/3}\log n)}\) by \textit{J. Fox} and \textit{J. Pach} [SODA 2011, 1161--1165 (2011; Zbl 1377.68275)], we investigate which problems have subexponential algorithms on the intersection graphs of curves (string graphs) or segments (segment intersection graphs) and which problems have no such algorithms under the ETH (Exponential Time Hypothesis). Among our results, we show that, quite surprisingly, 3-Coloring can also be solved in time \(2^{O(n^{2/3}\log ^{O(1)}n)}\) on string graphs while an algorithm running in time \(2^{o(n)}\) for 4-Coloring even on axis-parallel segments (of unbounded length) would disprove the ETH. For 4-Coloring of unit segments, we show a weaker lower bound, excluding a \(2^{o(n^{2/3})}\) algorithm (under the ETH). The construction exploits the celebrated Erdős-Szekeres theorem. The subexponential running time also carries over to Min Feedback Vertex Set, but not to Min Dominating Set and Min Independent Dominating Set.
For the entire collection see [Zbl 1398.68016].Simple and local independent set approximationhttps://zbmath.org/1517.682792023-09-22T14:21:46.120933Z"Boppana, Ravi B."https://zbmath.org/authors/?q=ai:boppana.ravi-b"Halldórsson, Magnús M."https://zbmath.org/authors/?q=ai:halldorsson.magnus-m"Rawitz, Dror"https://zbmath.org/authors/?q=ai:rawitz.drorSummary: We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a streaming and preemptive online algorithm. We show it gives a tight \((\varDelta+1)/2\)-approximation in unweighted graphs of maximum degree \(\varDelta\), which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a \((\varDelta+1)\)-approximation, but a simple modification results in an asymptotic expected \(0.529(\varDelta+1)\)-approximation. This compares with a recent, more complex \(\varDelta\)-approximation [\textit{R. Bar-Yehuda} et al., PODC 2017, 165--174 (2017; Zbl 1380.68416)], which holds deterministically.
For the entire collection see [Zbl 1400.68027].Temporal cliques admit sparse spannershttps://zbmath.org/1517.682802023-09-22T14:21:46.120933Z"Casteigts, Arnaud"https://zbmath.org/authors/?q=ai:casteigts.arnaud"Peters, Joseph G."https://zbmath.org/authors/?q=ai:peters.joseph-g"Schoeters, Jason"https://zbmath.org/authors/?q=ai:schoeters.jasonSummary: Let \(G=(V,E)\) be an undirected graph on \(n\) vertices and \(\lambda:E\to 2^{\mathbb{N}}\) a mapping that assigns to every edge a non-empty set of integer labels (discrete times when the edge is present). Such a labelled graph \(\mathcal{G}=(G,\lambda)\) is \textit{temporally connected} if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, \textit{D. Kempe} et al. [STOC 2000, 504--513 (2000; Zbl 1296.68015)] sked whether, given such a temporally connected graph, a \textit{sparse} subset of edges always exists whose labels suffice to preserve temporal connectivity -- a \textit{temporal spanner}. \textit{K. Axiotis} and \textit{D. Fotakis} [LIPIcs -- Leibniz Int. Proc. Inform. 55, Article 149, 14 p. (2016; Zbl 1388.68299)] answered negatively by exhibiting a family of \(\Theta(n^2)\)-dense temporal graphs which admit no temporal spanner of density \(o(n^2)\). In this paper, we give the first positive answer as to the existence of \(o(n^2)\)-sparse spanners in a dense class of temporal graphs, by showing (constructively) that if \(G\) is a complete graph, then one can always find a temporal spanner with \(O(n\log n)\) edges.Temporal cliques admit sparse spannershttps://zbmath.org/1517.682812023-09-22T14:21:46.120933Z"Casteigts, Arnaud"https://zbmath.org/authors/?q=ai:casteigts.arnaud"Peters, Joseph G."https://zbmath.org/authors/?q=ai:peters.joseph-g"Schoeters, Jason"https://zbmath.org/authors/?q=ai:schoeters.jasonSummary: Let \(G=(V,E)\) be an undirected graph on \(n\) vertices and \(\lambda:E\to 2^{\mathbb{N}}\) a mapping that assigns to every edge a non-empty set of positive integer labels. These labels can be seen as discrete times when the edge is present. Such a labeled graph \(\mathcal{G}=(G,\lambda)\) is said to be temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, \textit{D. Kempe} et al. [STOC 2000, 504--513 (2000; Zbl 1296.68015)] asked whether, given such a temporal graph, a sparse subset of edges can always be found whose labels suffice to preserve temporal connectivity -- a temporal spanner. \textit{K. Axiotis} and \textit{D. Fotakis} [LIPIcs -- Leibniz Int. Proc. Inform. 55, Article 149, 14 p. (2016; Zbl 1388.68299)] answered negatively by exhibiting a family of \(\Theta(n^2)\)-dense temporal graphs which admit no temporal spanner of density \(o(n^2)\). The natural question is then whether sparse temporal spanners always exist in some classes of dense graphs.\par In this paper, we answer this question affirmatively, by showing that if the underlying graph \(G\) is a complete graph, then one can always find temporal spanners of density \(O(n\log n)\). The best known result for complete graphs so far was that spanners of density \(\binom{n}{2}-\lfloor n/4\rfloor= O(n^2)\) always exist. Our result is the first positive answer as to the existence of \(o(n^2)\) sparse spanners in adversarial instances of temporal graphs since the original question by Kempe et al. [loc. cit.], focusing here on complete graphs. The proofs are constructive and directly adaptable as an algorithm.
For the entire collection see [Zbl 1414.68003].On the complexity of minimum maximal uniquely restricted matchinghttps://zbmath.org/1517.682822023-09-22T14:21:46.120933Z"Chaudhary, Juhi"https://zbmath.org/authors/?q=ai:chaudhary.juhi"Panda, B. S."https://zbmath.org/authors/?q=ai:panda.bhawani-sankarSummary: A subset \(M \subseteq E\) of edges of a graph \(G = (V, E)\) is called a \textit{matching} if no two edges of \(M\) share a common vertex. A matching \(M\) in a graph \(G\) is called a \textit{uniquely restricted matching} if, \(G [V(M)]\), the subgraph of \(G\) induced by the set of \(M\)-saturated vertices of \(G\) contains exactly one perfect matching. A uniquely restricted matching \(M\) is \textit{maximal} if \(M\) is not properly contained in any uniquely restricted matching of \(G\). Given a graph \(G\), the \textsc{Min-Max-UR Matching} problem asks to find a maximal uniquely restricted matching in \(G\) of minimum cardinality and \textsc{Decide-Min-Max-UR Matching} problem, the decision version of this problem takes a graph \(G\) and an integer \(k\) and asks whether \(G\) admits a maximal uniquely restricted matching of cardinality at most \(k\). It is known that the \textsc{Decide-Min-Max-UR Matching} problem is \(\mathsf{NP} \)-complete. In this paper, we strengthen this result by proving that the \textsc{Decide-Min-Max-UR Matching} problem remains \(\mathsf{NP} \)-complete for chordal bipartite graphs, star-convex bipartite graphs, chordal graphs, and doubly chordal graphs. On the positive side, we prove that the \textsc{Min-Max-UR Matching} problem is polynomial time solvable for bipartite distance-hereditary graphs and linear time solvable for bipartite permutation graphs, proper interval graphs, and threshold graphs. Finally, we prove that the \textsc{Min-Max-UR Matching} problem is \(\mathsf{APX} \)-complete for graphs with maximum degree 4.On the complexity of minimum maximal uniquely restricted matchinghttps://zbmath.org/1517.682832023-09-22T14:21:46.120933Z"Chaudhary, Juhi"https://zbmath.org/authors/?q=ai:chaudhary.juhi"Panda, B. S."https://zbmath.org/authors/?q=ai:panda.bhawani-sankarSummary: A subset \(M\subseteq E\) of edges of a graph \(G=(V,E)\) is called a \textit{matching} if no two edges of \(M\) share a common vertex. A matching \(M\) in a graph \(G\) is called a \textit{uniquely restricted matching} if \(G[V(M)]\), the subgraph of \(G\) induced by the \(M\)-saturated vertices of \(G\), contains exactly one perfect matching. A uniquely restricted matching \(M\) is \textit{maximal} if \(M\) is not properly contained in any other uniquely restricted matching of \(G\). Given a graph \(G\), the \textsc{Min-Max-UR Matching} problem asks to find a maximal uniquely restricted matching of minimum cardinality in \(G\). In general, the decision version of the \textsc{Min-Max-UR Matching} problem is known to be \({\mathsf{NP}} \)-complete for general graphs and remains so even for bipartite graphs. In this paper, we strengthen this result by proving that this problem remains \({\mathsf{NP}} \)-complete for chordal bipartite graphs and chordal graphs. On the positive side, we prove that the \textsc{Min-Max-UR Matching} problem is polynomial time solvable for bipartite permutation graphs and proper interval graphs. Finally, we show that the \textsc{Min-Max-UR Matching} problem is \(\mathsf{APX} \)-complete for bounded degree graphs.
For the entire collection see [Zbl 1507.68048].Constructing dual-CISTs with short diameters using a generic adjustment scheme on bicubeshttps://zbmath.org/1517.682842023-09-22T14:21:46.120933Z"Chen, Yu-Han"https://zbmath.org/authors/?q=ai:chen.yuhan"Tang, Shyue-Ming"https://zbmath.org/authors/?q=ai:tang.shyue-ming"Pai, Kung-Jui"https://zbmath.org/authors/?q=ai:pai.kung-jui"Chang, Jou-Ming"https://zbmath.org/authors/?q=ai:chang.jou-mingSummary: Recently, an innovative hypercube-variant network called bicube, denoted as \(B Q_n\), has been proposed to possess both short diameter and symmetry advantages. Unlike other existing hypercube-variant networks, they lose their symmetry in pursuit of short diameters. For solving the problems of fault-tolerant transmission and secure message distribution in a reliable network, one solution suggested a dual-CIST (two completely independent spanning trees) to design a multi-path routing (e.g., a recently proposed secure-protection routing). We can make the construction using the standard arrangement guideline (SAG) like the hypercubes to obtain a dual-CIST with a diameter of \(2 n - 1\) on \(B Q_n\). This paper proposes a newly generic adjustment scheme (GAS) for reducing the diameter of the dual-CIST under this construction. As a result, the diameter of \(T_i\) for \(i = 1, 2\) we constructed for \(B Q_n\) are as follows:
\[\operatorname{diam}(T_i) =
\begin{cases}
7 \quad & \text{if } n = 4 ; \\
2 n - 2 \quad & \text{if } n \geqslant 5 \text{ and } n \text{ is odd}; \\
2 n - 3 \quad & \text{if } n \geqslant 6 \text{ and } n \text{ is even}.
\end{cases}\]Independent sets in vertex-arrival streamshttps://zbmath.org/1517.682852023-09-22T14:21:46.120933Z"Cormode, Graham"https://zbmath.org/authors/?q=ai:cormode.graham"Dark, Jacques"https://zbmath.org/authors/?q=ai:dark.jacques"Konrad, Christian"https://zbmath.org/authors/?q=ai:konrad.christianSummary: We consider the maximal and maximum independent set problems in three models of graph streams:
\begin{itemize}\item[--] In the edge model we see a stream of edges which collectively define a graph; this model is well-studied for a variety of problems. We show that the space complexity for a one-pass streaming algorithm to find a maximal independent set is quadratic (i.e. we must store all edges). We further show that it is not much easier if we only require approximate maximality. This contrasts strongly with the other two vertex-based models, where one can greedily find an exact solution in only the space needed to store the independent set.\item[--] In the ``explicit'' vertex model, the input stream is a sequence of vertices making up the graph. Every vertex arrives along with its incident edges that connect to previously arrived vertices. Various graph problems require substantially less space to solve in this setting than in edge-arrival streams. We show that every one-pass \(c\)-approximation streaming algorithm for maximum independent set (MIS) on explicit vertex streams requires \(\Omega(\frac{n^2}{c^6})\) bits of space, where \(n\) is the number of vertices of the input graph. It is already known that \(\widetilde{\Theta}(\frac{n^2}{c^2})\) bits of space are necessary and sufficient in the edge arrival model [\textit{M. M. Halldórsson} et al., Lect. Notes Comput. Sci. 7391, 449--460 (2012; Zbl 1272.68333)], thus the MIS problem is not significantly easier to solve under the explicit vertex arrival order assumption. Our result is proved via a reduction from a new multi-party communication problem closely related to pointer jumping.\item[--] In the ``implicit'' vertex model, the input stream consists of a sequence of objects, one per vertex. The algorithm is equipped with a function that maps pairs of objects to the presence or absence of edges, thus defining the graph. This model captures, for example, geometric intersection graphs such as unit disc graphs. Our final set of results consists of several improved upper and lower bounds for interval and square intersection graphs, in both explicit and implicit streams. In particular, we show a gap between the hardness of the explicit and implicit vertex models for interval graphs.\end{itemize}
For the entire collection see [Zbl 1414.68003].Computing small pivot-minorshttps://zbmath.org/1517.682862023-09-22T14:21:46.120933Z"Dabrowski, Konrad K."https://zbmath.org/authors/?q=ai:dabrowski.konrad-kazimierz"Dross, François"https://zbmath.org/authors/?q=ai:dross.francois"Jeong, Jisu"https://zbmath.org/authors/?q=ai:jeong.jisu"Kanté, Mamadou Moustapha"https://zbmath.org/authors/?q=ai:kante.mamadou-moustapha"Kwon, O-joung"https://zbmath.org/authors/?q=ai:kwon.ojoung"Oum, Sang-il"https://zbmath.org/authors/?q=ai:oum.sang-il"Paulusma, Daniël"https://zbmath.org/authors/?q=ai:paulusma.danielSummary: A graph \(G\) contains a graph \(H\) as a pivot-minor if \(H\) can be obtained from \(G\) by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. However, so far, pivot-minors have only been studied from a structural perspective. We initiate a systematic study into their complexity aspects. We first prove that the Pivot-Minor problem, which asks if a given graph \(G\) contains a given graph \(H\) as a pivot-minor, is NP-complete. If \(H\) is not part of the input, we denote the problem by \(H\)-Pivot-Minor. We give a certifying polynomial-time algorithm for \(H\)-Pivot-Minor for every graph \(H\) with \(|V(H)|\leq 4\) except when \(H\in\{K_4,C_3+P_1,4P_1\}\), via a structural characterization of \(H\)-pivot-minor-free graphs in terms of a set \(\mathcal{F}_H\) of minimal forbidden induced subgraphs.
For the entire collection see [Zbl 1398.68016].Subexponential-time and FPT algorithms for embedded flat clustered planarityhttps://zbmath.org/1517.682872023-09-22T14:21:46.120933Z"Da Lozzo, Giordano"https://zbmath.org/authors/?q=ai:da-lozzo.giordano"Eppstein, David"https://zbmath.org/authors/?q=ai:eppstein.david"Goodrich, Michael T."https://zbmath.org/authors/?q=ai:goodrich.michael-t"Gupta, Siddharth"https://zbmath.org/authors/?q=ai:gupta.siddharthSummary: The C-Planarity problem asks for a drawing of a clustered graph, i.e., a graph whose vertices belong to properly nested clusters, in which each cluster is represented by a simple closed region with no edge-edge crossings, no region-region crossings, and no unnecessary edge-region crossings. We study C-Planarity for embedded flat clustered graphs, graphs with a fixed combinatorial embedding whose clusters partition the vertex set. Our main result is a subexponential-time algorithm to test C-Planarity for these graphs when their face size is bounded. Furthermore, we consider a variation of the notion of embedded tree decomposition in which, for each face, including the outer face, there is a bag that contains every vertex of the face. We show that C-Planarity is fixed-parameter tractable with the embedded-width of the underlying graph and the number of disconnected clusters as parameters.
For the entire collection see [Zbl 1398.68016].Saving probe bits by cube dominationhttps://zbmath.org/1517.682882023-09-22T14:21:46.120933Z"Damaschke, Peter"https://zbmath.org/authors/?q=ai:damaschke.peterSummary: We consider the problem of storing a single element from an \(m\)-element set as a binary string of optimal length, and comparing any queried string to the stored string without reading all bits. This is the one-element version of the problem of membership testing in the bit probe model, and solutions can serve as building blocks of general membership testers. Our principal contribution is the equivalence of saving probe bits with some generalized notion of domination in hypercubes. This domination variant requires that every vertex outside the dominating set belongs to a sub-hypercube, of fixed dimension, in which all other vertices belong to in the dominating set. This fixed dimension equals the number of saved probe bits. We give specific constructions showing that up to three probe bits can be ignored when \(m\) is far enough from the next larger power of 2. The main technical idea is to use low-dimensional (grid) relaxations of the problem. The design of optimal schemes remains an open problem, however one has to notice that even usual domination in hypercubes is far from being completely understood.
For the entire collection see [Zbl 1398.68016].Graph amalgamation under logical constraintshttps://zbmath.org/1517.682892023-09-22T14:21:46.120933Z"de Oliveira Oliveira, Mateus"https://zbmath.org/authors/?q=ai:de-oliveira-oliveira.mateusSummary: We say that a graph \(G\) is an \(H\)-amalgamation of graphs \(G_1\) and \(G_2\) if \(G\) can be obtained by gluing \(G_1\) and \(G_2\) along isomorphic copies of \(H\). In the Amalgamation Recognition problem we are given connected graphs \(H,G_1,G_2,G\) and the goal is to determine whether \(G\) is an \(H\)-amalgamation of \(G_1\) and \(G_2\). Our main result states that Amalgamation Recognition can be solved in time \(2^{O(\varDelta\cdot t)}\cdot n^{O(t)}\) where \(n,t,\varDelta\) are the number of vertices, the treewidth and the maximum degree of \(G\) respectively.
We generalize the techniques used in our algorithm for \(H\)-amalgamation recognition to the setting in which some of the graphs \(H,G_1,G_2,G\) are not given explicit at the input but are instead required to satisfy some topological property expressible in the counting monadic second order logic of graphs (CMSO logic). In this way, when restricting ourselves to graphs of constant treewidth and degree our approach generalizes certain algorithmic decomposition theorems from structural graph theory from the context of clique-sums to the context in which the interface graph \(H\) is given at the input.
For the entire collection see [Zbl 1398.68016].\(\forall\exists\mathbb {R}\)-completeness and area-universalityhttps://zbmath.org/1517.682902023-09-22T14:21:46.120933Z"Dobbins, Michael Gene"https://zbmath.org/authors/?q=ai:dobbins.michael-gene"Kleist, Linda"https://zbmath.org/authors/?q=ai:kleist.linda"Miltzow, Tillmann"https://zbmath.org/authors/?q=ai:miltzow.tillmann"Rzążewski, Paweł"https://zbmath.org/authors/?q=ai:rzazewski.pawelSummary: In the study of geometric problems, the complexity class \(\exists\mathbb{R}\) plays a crucial role since it exhibits a deep connection between purely geometric problems and real algebra. Sometimes \(\exists\mathbb {R}\) is referred to as the ``real analogue'' to the class NP. While NP is a class of computational problems that deals with existentially quantified Boolean variables, \(\exists\mathbb{R}\) deals with existentially quantified real variables.
In analogy to \(\varPi_2^p\) and \(\varSigma_2^p\) in the famous polynomial hierarchy, we study the complexity classes \(\forall\exists\mathbb{R}\) and \(\exists\forall\mathbb{R}\) with real variables. Our main interest is focused on the Area Universality problem, where we are given a plane graph \(G\), and ask if for each assignment of areas to the inner faces of \(G\) there is an area-realizing straight-line drawing of \(G\). We conjecture that the problem Area Universality is \(\forall\exists\mathbb{R}\)-complete and support this conjecture by a series of partial results, where we prove \(\exists\mathbb{R}\)- and \(\forall\exists\mathbb{R}\)-completeness of variants of Area Universality. To do so, we also introduce first tools to study \(\forall\exists\mathbb{R}\). Finally, we present geometric problems as candidates for \(\forall\exists\mathbb{R}\)-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.
For the entire collection see [Zbl 1398.68016].Measuring what matters: a hybrid approach to dynamic programming with treewidthhttps://zbmath.org/1517.682912023-09-22T14:21:46.120933Z"Eiben, Eduard"https://zbmath.org/authors/?q=ai:eiben.eduard"Ganian, Robert"https://zbmath.org/authors/?q=ai:ganian.robert"Hamm, Thekla"https://zbmath.org/authors/?q=ai:hamm.thekla"Kwon, O-joung"https://zbmath.org/authors/?q=ai:kwon.ojoungSummary: We develop a framework for applying treewidth-based dynamic programming on graphs with ``hybrid structure'', i.e., with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for \textsc{Chromatic Number}, \textsc{Hamiltonian Cycle}, and \textsc{Max-Cut}.Measuring what matters: a hybrid approach to dynamic programming with treewidthhttps://zbmath.org/1517.682922023-09-22T14:21:46.120933Z"Eiben, Eduard"https://zbmath.org/authors/?q=ai:eiben.eduard"Ganian, Robert"https://zbmath.org/authors/?q=ai:ganian.robert"Hamm, Thekla"https://zbmath.org/authors/?q=ai:hamm.thekla"Kwon, O-Joung"https://zbmath.org/authors/?q=ai:kwon.ojoungSummary: We develop a framework for applying treewidth-based dynamic programming on graphs with ``hybrid structure'', i.e., with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for Chromatic Number, Hamiltonian Cycle, and Max-Cut.
For the entire collection see [Zbl 1423.68036].Atomic embeddability, clustered planarity, and thickenabilityhttps://zbmath.org/1517.682932023-09-22T14:21:46.120933Z"Fulek, Radoslav"https://zbmath.org/authors/?q=ai:fulek.radoslav"Tóth, Csaba D."https://zbmath.org/authors/?q=ai:toth.csaba-dVoronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) timehttps://zbmath.org/1517.682942023-09-22T14:21:46.120933Z"Gawrychowski, Paweł"https://zbmath.org/authors/?q=ai:gawrychowski.pawel"Kaplan, Haim"https://zbmath.org/authors/?q=ai:kaplan.haim"Mozes, Shay"https://zbmath.org/authors/?q=ai:mozes.shay"Sharir, Micha"https://zbmath.org/authors/?q=ai:sharir.micha"Weimann, Oren"https://zbmath.org/authors/?q=ai:weimann.orenThere is a deterministic \(\tilde{O}(n^{5/3})\)-time algorithm, where \(\tilde{O}\) hides polylogarithmic factors, for computing the diameter of a directed planar graph on \(n\) vertices and without negative-length cycles.
Reviewer: Haiko Müller (Leeds)Covering a graph with nontrivial vertex-disjoint paths: existence and optimizationhttps://zbmath.org/1517.682952023-09-22T14:21:46.120933Z"Gómez, Renzo"https://zbmath.org/authors/?q=ai:gomez.renzo"Wakabayashi, Yoshiko"https://zbmath.org/authors/?q=ai:wakabayashi.yoshikoSummary: Let \(G\) be a connected graph and \(\mathcal{P}\) be a set of pairwise vertex-disjoint paths in \(G\). We say that \(\mathcal{P}\) is a path cover if every vertex of \(G\) belongs to a path in \(\mathcal{P}\). In the Minimum Path Cover problem, one wishes to find a path cover of minimum cardinality. In this problem, known to be \({\textsc{NP}}\)-hard, the set \(\mathcal{P}\) may contain trivial (single-vertex) paths. We study the problem of finding a path cover composed only of nontrivial paths. First, we show that the Corresponding Existence problem can be reduced to a matching problem on a bipartite graph via the Edmonds-Gallai Decomposition. This reduction gives, in polynomial time, a certificate for both the yes-answer and the no-answer. When trivial paths are forbidden, for the feasible instances, one may consider either minimizing or maximizing the number of paths in the path cover. We show that the maximization problem has a close relation with the maximum matchings of a graph, and can be solved in polynomial time. For the minimization problem on feasible instances, we show that its computational complexity is equivalent to the Minimum Path Cover problem. We also show a linear-time algorithm on (edge-weighted) trees.
For the entire collection see [Zbl 1398.68016].Certificates and fast algorithms for biconnectivity in fully-dynamic graphshttps://zbmath.org/1517.682962023-09-22T14:21:46.120933Z"Henzinger, Monika R."https://zbmath.org/authors/?q=ai:rauch-henzinger.monika"La Poutré, Han"https://zbmath.org/authors/?q=ai:la-poutre.hanSummary: In this paper, we present sparse certificates for biconnectivity together with algorithms for updating these certificates. We thus obtain fully-dynamic algorithms for biconnectivity in graphs that run in \(O(\sqrt{n \log n} \log \lceil\frac{m}{n}\rceil)\) amortized time per operation, where \(m\) is the number of edges and \(n\) is the number of nodes in the graph. This improves upon the results in [\textit{M. Rauch}, STOC 1994, 686--695 (1994; Zbl 1344.68062)], in which algorithms were presented running in \(O(\sqrt{m})\) amortized time, and solves the open problem to find certificates to speed up biconnectivity, as stated in [\textit{D. Eppstein} et al., FOCS 1992, 60--69 (1992; Zbl 0977.68560); J. ACM 44, No. 5, 669--696 (1997; Zbl 0891.68072)].
For the entire collection see [Zbl 0854.00022].Connectivity and minimum cut approximation in the broadcast congested cliquehttps://zbmath.org/1517.682972023-09-22T14:21:46.120933Z"Jurdziński, Tomasz"https://zbmath.org/authors/?q=ai:jurdzinski.tomasz"Nowicki, Krzysztof"https://zbmath.org/authors/?q=ai:nowicki.krzysztofSummary: In this paper we present two graph algorithms in the broadcast congested clique model. In this model, there are \(n\) players, which communicate in synchronous rounds. Each player represents a single node of the input graph; initially each player knows the set of edges incident to his node. In each round of communication each node can broadcast a single \(b\)-bit message to all other nodes; usually \(b\in{\mathcal{O}}(\log n)\). The goal is to compute some function of the input graph.
The first result we present is the first sub-logarithmic deterministic algorithm finding a maximal spanning forest of an \(n\) node graph in the broadcast congested clique, which requires only \({\mathcal{O}}(\log n/\log\log n)\) rounds. The second result is a randomized \(1+\epsilon\) approximation algorithm finding the minimum cut of an \(n\) node graph, which requires only \({\mathcal{O}}(\log n)\) maximal spanning forest computations. In the broadcast congested clique this approach, combined with the new maximal spanning forest algorithm, yields an \({\mathcal{O}}(\log^2 n/\log\log n)\) round algorithm. Additionally, it may be applied to different models, i.e. in the multi-pass semi-streaming model it allows to reduce required memory by \(\varTheta(\log n)\) factor, with only \({\mathcal{O}}(\log^* n)\) passes over the data stream.
For the entire collection see [Zbl 1400.68027].Convexity-increasing morphs of planar graphshttps://zbmath.org/1517.682982023-09-22T14:21:46.120933Z"Kleist, Linda"https://zbmath.org/authors/?q=ai:kleist.linda"Klemz, Boris"https://zbmath.org/authors/?q=ai:klemz.boris"Lubiw, Anna"https://zbmath.org/authors/?q=ai:lubiw.anna"Schlipf, Lena"https://zbmath.org/authors/?q=ai:schlipf.lena"Staals, Frank"https://zbmath.org/authors/?q=ai:staals.frank"Strash, Darren"https://zbmath.org/authors/?q=ai:strash.darrenSummary: We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of a 3-connected graph \(G\), we show how to morph the drawing to one with convex faces while maintaining planarity at all times. Furthermore, the morph is convexity increasing, meaning that angles of inner faces never change from convex to reflex. We give a polynomial time algorithm that constructs such a morph as a composition of a linear number of steps where each step either moves vertices along horizontal lines or moves vertices along vertical lines.
For the entire collection see [Zbl 1398.68016].Deterministic distributed ruling sets of line graphshttps://zbmath.org/1517.682992023-09-22T14:21:46.120933Z"Kuhn, Fabian"https://zbmath.org/authors/?q=ai:kuhn.fabian"Maus, Yannic"https://zbmath.org/authors/?q=ai:maus.yannic"Weidner, Simon"https://zbmath.org/authors/?q=ai:weidner.simonSummary: An \((\alpha,\beta)\)-ruling set of a graph \(G=(V,E)\) is a set \(R\subseteq V\) such that for any node \(v\in V\) there is a node \(u\in R\) in distance at most \(\beta\) from \(v\) and such that any two nodes in \(R\) are at distance at least \(\alpha\) from each other. The concept of ruling sets can naturally be extended to edges, i.e., a subset \(F\subseteq E\) is an \((\alpha,\beta)\)-ruling edge set of a graph \(G=(V,E)\) if the corresponding nodes form an \((\alpha,\beta)\)-ruling set in the line graph of \(G\). This paper presents a simple deterministic, distributed algorithm, in the \(\mathsf{CONGEST}\) model, for computing (2, 2)-ruling edge sets in \(O(\log ^{*}n)\) rounds. Furthermore, we extend the algorithm to compute ruling sets of graphs with bounded diversity. Roughly speaking, the diversity of a graph is the maximum number of maximal cliques a vertex belongs to. We devise \((2,O(\mathcal{D}))\)-ruling sets on graphs with diversity \(\mathcal{D}\) in \(O(\mathcal{D}+\log^{*}n)\) rounds. This also implies a fast, deterministic \((2,O(\ell))\)-ruling edge set algorithm for hypergraphs with rank at most \(\ell\).
Furthermore, we provide a ruling set algorithm for general graphs that for any \(B\geq 2\) computes an \(\big(\alpha,\alpha\lceil\log_B n\rceil\big)\)-ruling set in \(O(\alpha\cdot B\cdot\log_B n)\) rounds in the \(\mathsf{CONGEST}\) model. The algorithm can be modified to compute a \(\big(2,\beta\big)\)-ruling set in \(O(\beta\varDelta^{2/\beta}+\log^{*}n)\) rounds in the \(\mathsf{CONGEST}\) model, which matches the currently best known such algorithm in the more general \(\mathsf{LOCAL}\) model.
For the entire collection see [Zbl 1400.68027].The component (edge) connectivity of round matching composition networkshttps://zbmath.org/1517.683002023-09-22T14:21:46.120933Z"Liu, Xiaoqing"https://zbmath.org/authors/?q=ai:liu.xiaoqing"Zhou, Shuming"https://zbmath.org/authors/?q=ai:zhou.shuming"Zhang, Hong"https://zbmath.org/authors/?q=ai:zhang.hong.13"Niu, Baohua"https://zbmath.org/authors/?q=ai:niu.baohuaSummary: The vertex (edge) connectivity has been regularly used to measure the fault tolerance and reliability of interconnection networks, while it has defects in the assumption that all neighbors of one node will fail concurrently. To overcome this deficiency, some new generalizations of traditional connectivity have been suggested to quantize the size or the number of the connected components of the survival graph. The \(g\)-component (edge) connectivity, one generalization of vertex (edge) connectivity, has been proposed to characterize the vulnerability of multiprocessor systems based on the number of components of the survival graph. In this paper, we determine the \(g\)-component (edge) connectivity of a family of networks, called the round matching composition networks RMCNs, which are a class of networks composed of \(t\) \((t\geq 4)\) clusters with the same order, linked by \(r\) perfect matchings. By exploring the combinatorial properties and fault-tolerance of RMCNs, we establish the \(g\)-component (edge) connectivity \(c\kappa_{g+1}(G)=gk- g^2+3g\) for \(2\leq g\leq k+3\) and \(k\geq 2\), \(c\lambda_3(G)=2k+3\) and \(c\lambda_4(G)=3k+4\) for \(k\geq 4\).Construction and local routing for angle-monotone graphshttps://zbmath.org/1517.683012023-09-22T14:21:46.120933Z"Lubiw, Anna"https://zbmath.org/authors/?q=ai:lubiw.anna"Mondal, Debajyoti"https://zbmath.org/authors/?q=ai:mondal.debajyotiSummary: A geometric graph in the plane is angle-monotone of width \(\gamma\) if every pair of vertices is connected by an angle-monotone path of width \(\gamma\), a path such that the angles of any two edges in the path differ by at most \(\gamma\). Angle-monotone graphs have good spanning properties.
We prove that every point set in the plane admits an angle-monotone graph of width \(90^\circ\), hence with spanning ratio \(\sqrt{2}\), and a subquadratic number of edges. This answers an open question posed by \textit{H. R. Dehkordi} et al. [J. Graph Algorithms Appl. 19, No. 2, 761--778 (2015; Zbl 1328.05054)].
We show how to construct, for any point set of size \(n\) and any angle \(\alpha\), \(0<\alpha<45^\circ\), an angle-monotone graph of width \((90^\circ+\alpha)\) with \(O(\frac{n}{\alpha})\) edges. Furthermore, we give a local routing algorithm to find angle-monotone paths of width \((90^\circ+\alpha)\) in these graphs. The routing ratio, which is the ratio of path length to Euclidean distance, is at most \(1/\cos(45^\circ+\frac{\alpha}{2})\), i.e., ranging from \(\sqrt{2}\approx 1.414\) to 2.613. For the special case \(\alpha=30^\circ\), we obtain the \(\varTheta_6\)-graph and our routing algorithm achieves the known routing ratio 2 while finding angle-monotone paths of width \(120^\circ\).
For the entire collection see [Zbl 1398.68016].Approximability of open \(k\)-monopoly problemshttps://zbmath.org/1517.683022023-09-22T14:21:46.120933Z"Mishra, Sounaka"https://zbmath.org/authors/?q=ai:mishra.sounaka"Krishna, B. Arjuna"https://zbmath.org/authors/?q=ai:krishna.b-arjuna"Rajakrishnan, Shijin"https://zbmath.org/authors/?q=ai:rajakrishnan.shijinSummary: We consider approximability of two optimization problems called Minimum Open \(k\)-Monopoly (Min-Open-\(k\)-Monopoly) and Minimum Partial Open \(k\)-Monopoly (Min-P-Open-\(k\)-Monopoly), where \(k\) is a fixed positive integer. The objective, in Min-Open-\(k\)-Monopoly, is to find a minimum cardinality vertex set \(S\subseteq V\) in a given graph \(G=(V,E)\) such that \(|N(v)\cap S|\geq\frac{1}{2}|N(v)|+k\), for every vertex \(v \in V\). On the other hand, given a graph \(G=(V,E)\), in Min-P-Open-\(k\)-Monopoly it is required to find a minimum cardinality vertex set \(S\subseteq V\) such that \(|N(v)\cap S|\geq\frac{1}{2} |N(v)|+k\), for every \(v\in V\setminus S\). We prove that Min-Open-\(k\)-Monopoly and Min-P-Open-\(k\)-Monopoly are approximable within a factor of \(O(\log n)\). Then, we show that these two problems cannot be approximated within a factor of \((\frac{1}{3}- \epsilon)\ln n\) and \((\frac{1}{4}-\epsilon)\ln n\), respectively, for any \(\varepsilon>0\), unless \(\mathsf{NP}\subseteq\mathsf{Dtime}(n^{O(\log\log n)})\). For 4-regular graphs, we prove that these two problems are \textsf{APX}-complete. Min-Open-1-Monopoly can be approximated within a factor of \(\frac{26}{21}\approx 1.2381\) where as Min-P-Open-1-Monopoly can be approximated within a factor of 1.65153. For \(k\geq 2\), we also present approximation algorithms for these two problems for \((2k+2)\)-regular graphs.Two rounds are enough for reconstructing any graph (class) in the congested clique modelhttps://zbmath.org/1517.683032023-09-22T14:21:46.120933Z"Montealegre, Pedro"https://zbmath.org/authors/?q=ai:montealegre.pedro"Perez-Salazar, Sebastian"https://zbmath.org/authors/?q=ai:perez-salazar.sebastian"Rapaport, Ivan"https://zbmath.org/authors/?q=ai:rapaport.ivan"Todinca, Ioan"https://zbmath.org/authors/?q=ai:todinca.ioanSummary: In this paper we study the reconstruction problem in the congested clique model. In the reconstruction problem nodes are asked to recover all the edges of the input graph \(G\). Formally, given a class of graphs \(\mathcal G\), the problem is defined as follows: if \(G \notin{\mathcal G}\), then every node must reject; on the other hand, if \(G\in{\mathcal G}\), then every node must end up knowing all the edges of \(G\). It is not difficult to see that the cost \(Rb\) of any algorithm that solves this problem (even with public coins) is at least \(\varOmega(\log|{\mathcal{G}}_n|/n)\), where \({\mathcal{G}}_n\) is the subclass of all \(n\)-node labeled graphs in \(\mathcal G\), \(R\) is the number of rounds and \(b\) is the bandwidth.
We prove here that the lower bound above is in fact tight and that it is possible to achieve it with only \(R=2\) rounds and private coins. More precisely, we exhibit (i) a one-round algorithm that achieves this bound for hereditary graph classes; and (ii) a two-round algorithm that achieves this bound for arbitrary graph classes. Later, we show that the bound \(\varOmega(\log|{\mathcal{G}}_n|/n)\) cannot be achieved in one round for arbitrary graph classes, and we give tight algorithms for that case.
From (i) we recover all known results concerning the reconstruction of graph classes in one round and bandwidth \(\mathcal{O}(\log n)\): forests, planar graphs, cographs, etc. But we also get new one-round algorithms for other hereditary graph classes such as unit-disc graphs, interval graphs, etc. From (ii), we can conclude that any problem restricted to a class of graphs of size \(2^{\mathcal{O}(n\log n)}\) can be solved in the congested clique model in two rounds, with bandwidth \(\mathcal{O}(\log n)\). Moreover, our general two-round algorithm is valid for any set of labeled graphs, not only for graph classes.
For the entire collection see [Zbl 1400.68027].A polyhedral approach to planar augmentation and related problemshttps://zbmath.org/1517.683042023-09-22T14:21:46.120933Z"Mutzel, Petra"https://zbmath.org/authors/?q=ai:mutzel.petraSummary: Given a planar graph \(G\), the planar (biconnectivity) augmentation problem is to add the minimum number of edges to \(G\) such that the resulting graph is still planar and biconnected. Given a nonplanar and biconnected graph, the maximum planar biconnected subgraph problem consists of removing the minimum number of edges so that planarity is achieved and biconnectivity is maintained. Both problems are important in Automatic Graph Drawing. In [\textit{M. Jünger} and the author, Lect. Notes Comput. Sci. 894, 119--130 (1994; \url{doi:10.1007/3-540-58950-3_363}), contained in Zbl 0806.68007], the minimum planarizing \(k\)-augmentation problem has been introduced, that links the planarization step and the augmentation step together. Here, we are given a graph which is not necessarily planar and not necessarily \(k\)-connected, and we want to delete some set of edges \(D\) and to add some set of edges \(A\) such that \(|D| + |A|\) is minimized and the resulting graph is planar, \(k\)-connected and spanning. For all three problems, we have given a polyhedral formulation by defining three different linear objective functions over the same polytope, namely the 2-node connected planar spanning subgraph polytope 2-\(\mathcal{NCPLS}(K_n)\). We investigate the facial structure of this polytope for \(k=2\), which we will make use of in a branch and cut algorithm. Here, we give the dimension of the planar, biconnected, spanning subgraph polytope for \(G=K_n\) and we show that all facets of the planar subgraph polytope \(\mathcal{PLS}(K_)n\) are also facets of the new polytope 2-\(\mathcal{NCPLS}(K_n)\). Furthermore, we show that the node-cut constraints arising in the biconnectivity spanning subgraph polytope, are facet-defining inequalities for 2-\(\mathcal{NCPLS}(K_n)\). We give first computational results for all three problems, the planar 2-augmentation problem, the minimum planarizing 2-augmentation problem and the maximum planar biconnected (spanning) subgraph problem. This is the first time that instances of any of these three problems can be solved to optimality.
For the entire collection see [Zbl 0854.00022].On the maximum edge-pair embedding bipartite matchinghttps://zbmath.org/1517.683052023-09-22T14:21:46.120933Z"Nguyen, Cam Ly"https://zbmath.org/authors/?q=ai:nguyen.cam-ly"Suppakitpaisarn, Vorapong"https://zbmath.org/authors/?q=ai:suppakitpaisarn.vorapong"Surarerks, Athasit"https://zbmath.org/authors/?q=ai:surarerks.athasit"Vajanopath, Phanu"https://zbmath.org/authors/?q=ai:vajanopath.phanuSummary: Given a set of edge pairs in a bipartite graph, we want to find a bipartite matching that includes a maximum number of those edge pairs. While the problem has many applications to wireless localization, to the best of our knowledge, there is no theoretical work for the problem. In this work, unless \(\mathrm{P = NP}\), we show that there is no constant approximation for the problem. Suppose that \(k\) denotes the maximum number of input edge pairs such that a particular node can be in. Inspired by experimental results, we consider the case that \(k\) is small. While there is a simple polynomial-time algorithm for the problem when \(k\) is one, we show that the problem is NP-hard when \(k\) is greater than one. We also devise an efficient \(O(k)\)-approximation algorithm for the problem.
For the entire collection see [Zbl 1435.68040].On the maximum edge-pair embedding bipartite matchinghttps://zbmath.org/1517.683062023-09-22T14:21:46.120933Z"Nguyen, Cam Ly"https://zbmath.org/authors/?q=ai:nguyen.cam-ly"Suppakitpaisarn, Vorapong"https://zbmath.org/authors/?q=ai:suppakitpaisarn.vorapong"Surarerks, Athasit"https://zbmath.org/authors/?q=ai:surarerks.athasit"Vajanopath, Phanu"https://zbmath.org/authors/?q=ai:vajanopath.phanuSummary: Given a set of edge pairs in a complete bipartite graph, we want to find a bipartite matching that includes the maximum number of those edge pairs. While the problem has many applications to wireless localization and computer vision, to the best of our knowledge, there is no theoretical work for the problem. In this work, unless \(\mathrm{P = NP}\), we show that there is no constant approximation for the problem. Then, we consider two special cases of the problem. Suppose that \(k\) denotes the maximum number of input edge pairs such that a particular node can be in. Inspired by experimental results, the first case is for when \(k\) is not large. While there is a simple polynomial-time algorithm for the problem when \(k\) is one, we show that the problem is NP-hard when \(k\) is greater than one. We also devise an efficient \(O(k)\)-approximation algorithm for the problem. For the second case, every pair of nodes in the same partition of the input bipartite graph are labeled with one of \(\chi\) colors. We want to match, between the two partitions, a pair of nodes to a pair of nodes with the same color. Denote \(n\) as the number of nodes, we give an \(O(\sqrt{ \chi n})\)-approximation algorithm for this case.Explorable families of graphshttps://zbmath.org/1517.683072023-09-22T14:21:46.120933Z"Pelc, Andrzej"https://zbmath.org/authors/?q=ai:pelc.andrzejSummary: Graph exploration is one of the fundamental tasks performed by a mobile agent in a graph. An \(n\)-node graph has unlabeled nodes, and all ports at any node of degree \(d\) are arbitrarily numbered \(0,\dots,d-1\). A mobile agent, initially situated at some starting node \(v\), has to visit all nodes of the graph and stop. In the absence of any initial knowledge of the graph the task of deterministic exploration is often impossible. On the other hand, for some families of graphs it is possible to design deterministic exploration algorithms working for any graph of the family. We call such families of graphs explorable. Examples of explorable families are all finite families of graphs, as well as the family of all trees.
In this paper we study the problem of which families of graphs are explorable. We characterize all such families, and then ask the question whether there exists a universal deterministic algorithm that, given an explorable family of graphs, explores any graph of this family, without knowing which graph of the family is being explored. The answer to this question turns out to depend on how the explorable family is given to the hypothetical universal algorithm. If the algorithm can get the answer to any yes/no question about the family, then such a universal algorithm can be constructed. If, on the other hand, the algorithm can be only given an algorithmic description of the input explorable family, then such a universal deterministic algorithm does not exist.
For the entire collection see [Zbl 1400.68027].Faster parameterized algorithm for cluster vertex deletionhttps://zbmath.org/1517.683082023-09-22T14:21:46.120933Z"Tsur, Dekel"https://zbmath.org/authors/?q=ai:tsur.dekelSummary: In the \textsc{Cluster Vertex Deletion} problem the input is a graph \(G\) and an integer \(k\). The goal is to decide whether there is a set of vertices \(S\) of size at most \(k\) such that the deletion of the vertices of \(S\) from \(G\) results in a graph in which every connected component is a clique. We give an algorithm for \textsc{Cluster Vertex Deletion} whose running time is \(O^\ast (1.811^k)\).Fault-tolerant strong Menger (edge) connectivity of DCC linear congruential graphshttps://zbmath.org/1517.683092023-09-22T14:21:46.120933Z"Yu, Zhengqin"https://zbmath.org/authors/?q=ai:yu.zhengqin"Zhou, Shuming"https://zbmath.org/authors/?q=ai:zhou.shuming"Zhang, Hong"https://zbmath.org/authors/?q=ai:zhang.hong.13Summary: With the rapid development and advances of very large scale integration technology and wafer-scale integration technology, multiprocessor systems, taking interconnection networks as underlying topologies, have been widely designed and used in big data era. The topology of an interconnection network is usually represented as a graph. If any two distinct vertices \(x,y\) in a connected graph \(G\) are connected by \(\min\{\deg_G(x),\deg_G(y)\}\) vertex (edge)-disjoint paths, then \(G\) is called strongly Menger (edge) connected.
In [IEEE Trans. Comput. 45, No. 2, 156--164 (1996; Zbl 1068.68559)], \textit{J. Opatrny} et al. introduced the DCC (Disjoint Consecutive Cycle) linear congruential graph, which consists of \(n\) nodes and is generated by a set of linear functions \(F\) with special properties. In this work, we investigate the strong Menger connectivity of the DCC linear congruential graph \(\mathcal{G}= G_{2t}(F,2^p)\) with faulty vertices or edges, where \(2\leq t\leq p-1\), \(p\geq 5\), \(F=\{f_i(x)\mid f_i(x)=(2^{i-1}b+1)x+2^{i-1}c,1\leq i\leq t\}\), \(\gcd(c,2^p)=1\) and \(b\) is a multiple of \(4\). In detail, we show that \(\mathcal{G}-S\) is strongly Menger connected if \(|S|\leq 2t-4\) for any \(S\subseteq V(\mathcal{G})\). Moreover, we determine that \(\mathcal{G}-S\) is strongly Menger edge connected if \(|S|\leq 2t-2\) for any \(S\subseteq E(\mathcal{G})\). Furthermore, we prove that, under the restricted condition \(\delta(\mathcal{G}-S)\geq 2\), \(\mathcal{G}-S\) is strongly Menger edge connected if \(|S|\leq 4t-6\) and \(t\geq 3\) for any \(S\subseteq E(\mathcal{G})\). In addition, we present some empirical examples to show that the bounds are all optimal in the sense of the maximum number of tolerable edge faults.Structure and substructure connectivity of divide-and-swap cubehttps://zbmath.org/1517.683102023-09-22T14:21:46.120933Z"Zhou, Qianru"https://zbmath.org/authors/?q=ai:zhou.qianru"Zhou, Shuming"https://zbmath.org/authors/?q=ai:zhou.shuming"Liu, Jiafei"https://zbmath.org/authors/?q=ai:liu.jiafei"Liu, Xiaoqing"https://zbmath.org/authors/?q=ai:liu.xiaoqingSummary: High fault tolerance and reliability of multiprocessor systems, modeled by interconnection network, are of great significance to assess the flexibility and effectiveness of the systems. Connectivity is an important metric to evaluate the fault tolerance and reliability of interconnection networks. As classical connectivity is not suitable for such large scale systems, a novel and generalized connectivity, structure connectivity and substructure connectivity, has been proposed to measure the robustness of networks and has witnessed rich achievements. The divide-and-swap cube \(\mathit{DSC}_n\) is an interesting variant of hypercube that has nice hierarchical properties. In this paper, we mainly investigate \(\mathcal{H} \)-structure-connectivity, denoted by \(\kappa(\mathit{DSC}_n; \mathcal{H})\), and \(\mathcal{H} \)-substructure-connectivity, denoted by \(\kappa^s(\mathit{DSC}_n; \mathcal{H})\), for \(\mathcal{H} \in \{ K_1, K_{1 , 1}, K_{1 , m}(2 \leq m \leq d + 1), C_4 \} \), respectively. In detail, we show that \(\kappa(\mathit{DSC}_n; K_1) = \kappa^s(\mathit{DSC}_n; K_1) = d + 1\) for \(n \geq 2\), \(\kappa(\mathit{DSC}_n; K_{1 , 1}) = \kappa^s(\mathit{DSC}_n; K_{1 , 1}) = d + 1\) for \(n \geq 8\), \(\kappa(\mathit{DSC}_n; K_{1 , m}) = \kappa^s(\mathit{DSC}_n; K_{1 , m}) = \lfloor \frac{ d}{ 2} \rfloor + 1\) with \(2 \leq m \leq d + 1\) for \(n \geq 4\), \(\kappa(\mathit{DSC}_n; C_4) = 3 + 2(d - 2)\) for \(4 \leq n \leq 8\), \(\lfloor \frac{ d}{ 2} \rfloor + 1 \leq \kappa(\mathit{DSC}_n; C_4) \leq d + 1\) for \(n \geq 16\) and \(\kappa^s(\mathit{DSC}_n; C_4) = \lfloor \frac{ d}{ 2} \rfloor + 1\) for \(n \geq 4\). Finally, we compare and analyze the ratios of structure (resp. substructure) connectivity to vertex degree of divide-and-swap cube with that of several well-known variants of hypercube.Statistics on bargraphs of Catalan wordshttps://zbmath.org/1517.683112023-09-22T14:21:46.120933Z"Callan, David"https://zbmath.org/authors/?q=ai:callan.david"Mansour, Toufik"https://zbmath.org/authors/?q=ai:mansour.toufik"Ramírez, José L."https://zbmath.org/authors/?q=ai:ramirez.jose-luisSummary: Catalan words are a particular case of growth-restricted words. Here we give the bivariate generating function for bargraphs associated to Catalan words according to the semiperimeter and area statistics. Exact formulas to count Catalan bargraphs according to the two statistics are also found. We show a connection to the Narayana numbers. Finally, we give similar results for the exterior corner statistic.Transfinite Lyndon wordshttps://zbmath.org/1517.683122023-09-22T14:21:46.120933Z"Carton, Olivier"https://zbmath.org/authors/?q=ai:carton.olivier"Boasson, Luc"https://zbmath.org/authors/?q=ai:boasson.lucSummary: In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are densely non-increasing, a relaxation of the condition used in the case of finite words.
In the annex, we prove that the factorization of a rational word has a special form and that it can be computed from a rational expression describing the word.
For the conference paper see [DLT 2015, Lect. Notes Comput. Sci. 9168, 179--190 (2015; Zbl 1434.68378)].Simon's theorem for scattered wordshttps://zbmath.org/1517.683132023-09-22T14:21:46.120933Z"Carton, Olivier"https://zbmath.org/authors/?q=ai:carton.olivier"Pouzet, Maurice"https://zbmath.org/authors/?q=ai:pouzet.mauriceSummary: In this paper, we extend Simon's theorem to scattered words. We consider words whose length is a countable scattered linear orderings. We give an algebraic characterization of Boolean combinations of \(\preccurlyeq\)-upper sets where \(\preccurlyeq\) is the subword relation, also known as embedding on words.
For the entire collection see [Zbl 1398.68030].On the complexity of the generalized Fibonacci wordshttps://zbmath.org/1517.683142023-09-22T14:21:46.120933Z"Cassaigne, Julien"https://zbmath.org/authors/?q=ai:cassaigne.julien"Kaboré, Idrissa"https://zbmath.org/authors/?q=ai:kabore.idrissaThe well-known Fibonacci infinite word \(F=abaababaabaab\cdots\) can be obtained as the limit of the iteration of the morphism \(a\mapsto ab\), \(b\mapsto a\). The authors consider the \textit{generalized Fibonacci words} \(F_{l,m}\), which can be obtained as the limit of the iteration of the morphisms of the form \(a\mapsto a^lb^m\), \(b\mapsto a\), for \(l\geq 1\), \(m\geq 2\). In particular, the authors are interested in the factor complexity of these words -- recall that the factor complexity \(p(n)\) is the function that counts, for every \(n\geq 0\), the number of distinct factors of length \(n\).
The authors prove that the factor complexity of any generalized Fibonacci word satisfies
\[
n+1 \ \leq \ p(n) \ \leq \ 3n+1.
\]
Moreover,
\[
\text{ if }m\in[2,2l^2+1],\text{ then }1 \ < \ \lim \inf\ \frac{p(n)}{n} \ < \ \lim \sup\ \frac{p(n)}{n} \ < \ 2;
\]
\[
\text{ if }m>2l^2+1,\text{ then } 2 \ < \ \lim \inf\ \frac{p(n)}{n} \ < \ \lim \sup\ \frac{p(n)}{n} \ < \ 3.
\]
Reviewer: Gabriele Fici (Palermo)Upper bounds on the length of minimal solutions to certain quadratic word equationshttps://zbmath.org/1517.683152023-09-22T14:21:46.120933Z"Day, Joel D."https://zbmath.org/authors/?q=ai:day.joel-d"Manea, Florin"https://zbmath.org/authors/?q=ai:manea.florin"Nowotka, Dirk"https://zbmath.org/authors/?q=ai:nowotka.dirkSummary: It is a long standing conjecture that the problem of deciding whether a quadratic word equation has a solution is in NP. It has also been conjectured that the length of a minimal solution to a quadratic equation is at most exponential in the length of the equation, with the latter conjecture implying the former. We show that both conjectures hold for some natural subclasses of quadratic equations, namely the classes of regular-reversed, \(k\)-ordered, and variable-sparse quadratic equations. We also discuss a connection of our techniques to the topic of unavoidable patterns, and the possibility of exploiting this connection to produce further similar results.
For the entire collection see [Zbl 1423.68036].Block palindromes: a new generalization of palindromeshttps://zbmath.org/1517.683162023-09-22T14:21:46.120933Z"Goto, Keisuke"https://zbmath.org/authors/?q=ai:goto.keisuke"Tomohiro, I"https://zbmath.org/authors/?q=ai:tomohiro.itagaki"Bannai, Hideo"https://zbmath.org/authors/?q=ai:bannai.hideo"Inenaga, Shunsuke"https://zbmath.org/authors/?q=ai:inenaga.shunsukeSummary: We study a new generalization of palindromes and gapped palindromes called \textit{block palindromes}. A block palindrome is a string that becomes a palindrome when identical substrings are replaced with a distinct character. We investigate several properties of block palindromes and in particular, study substrings of a string which are block palindromes. In so doing, we introduce the notion of a \textit{maximal block palindrome}, which leads to a compact representation of all block palindromes that occur in a string. We also propose an algorithm which enumerates all maximal block palindromes that appear in a given string \(T\) in \(O(|T| + \Vert \operatorname{MBP} (T)\Vert )\) time, where \(\Vert \operatorname{MBP}(T)\Vert\) is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.
For the entire collection see [Zbl 1398.68028].On abelian subshiftshttps://zbmath.org/1517.683172023-09-22T14:21:46.120933Z"Karhumäki, Juhani"https://zbmath.org/authors/?q=ai:karhumaki.juhani"Puzynina, Svetlana"https://zbmath.org/authors/?q=ai:puzynina.svetlana"Whiteland, Markus A."https://zbmath.org/authors/?q=ai:whiteland.markus-aSummary: Two finite words \(u\) and \(v\) are called abelian equivalent if each letter occurs equally many times in both \(u\) and \(v\). The abelian subshift \(\mathcal A_{\boldsymbol{x}}\) of an infinite word \(\boldsymbol{x}\) is the set of infinite words \(\boldsymbol{y}\) such that, for each factor \(u\) of \(\boldsymbol{y}\), there exists a factor \(v\) of \(\boldsymbol{x}\) which is abelian equivalent to \(u\). The notion of abelian subshift gives a characterization of Sturmian words: among binary uniformly recurrent words, Sturmian words are exactly those words for which \(\mathcal A_{\boldsymbol{x}}\) equals the shift orbit closure \(\varOmega _{\boldsymbol{x}}\). On the other hand, the abelian subshift of the Thue-Morse word contains uncountably many minimal subshifts. In this paper we undertake a general study of abelian subshifts. In particular, we characterize the abelian subshifts of recurrent aperiodic balanced words and the abelian subshifts of ternary words having factor complexity \(n+2\) for all \(n\geq 1\).
For the entire collection see [Zbl 1398.68030].Involutive Fibonacci wordshttps://zbmath.org/1517.683182023-09-22T14:21:46.120933Z"Kari, Lila"https://zbmath.org/authors/?q=ai:kari.lila"Kulkarni, Manasi S."https://zbmath.org/authors/?q=ai:kulkarni.manasi-s"Mahalingam, Kalpana"https://zbmath.org/authors/?q=ai:mahalingam.kalpana"Wang, Zihao"https://zbmath.org/authors/?q=ai:wang.zihaoSummary: ``Fibonacci strings'' were first defined by \textit{D. E. Knuth} in his [The art of computer programming. Vol. 1: Fundamental algorithms. London: Addison-Wesley Publishing Company (1968; Zbl 0191.17903)] as being an infinite sequence of strings obtained from two initial letters \(f_1 =a\) and \(f_2 =b\), by the recursive definition \(f_{n+2}=f_{n+1} \cdot f_n\), for all positive integers \(n \geq 1\), where ``\(\cdot\)'' denotes word concatenation. In this paper, we first propose a unified terminology that allows readers to identify the different types of Fibonacci words, and corresponding results, that appear under the umbrella term ``Fibonacci words'' in the extensive literature on the topic. Motivated by ideas stemming from theoretical studies of DNA computing, we then define and exploreinvolutive Fibonacci words \((\phi\)-Fibonacci words and indexed \(\phi\)-Fibonacci words, where \(\phi\) denotes either a morphic or an antimorphic involution), and study various properties of such words.Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibilityhttps://zbmath.org/1517.683192023-09-22T14:21:46.120933Z"Lin, Anthony W."https://zbmath.org/authors/?q=ai:lin.anthony-widjaja"Majumdar, Rupak"https://zbmath.org/authors/?q=ai:majumdar.rupakSummary: Word equations are a crucial element in the theoretical foundation of constraint solving over strings. A word equation relates two words over string variables and constants. Its solution amounts to a function mapping variables to constant strings that equate the left and right hand sides of the equation. While the problem of solving word equations is decidable, the decidability of the problem of solving a word equation with a length constraint (i.e., a constraint relating the lengths of words in the word equation) has remained a long-standing open problem. We focus on the subclass of quadratic word equations, i.e., in which each variable occurs at most twice. We first show that the length abstractions of solutions to quadratic word equations are in general not Presburger-definable. We then describe a class of counter systems with Presburger transition relations which capture the length abstraction of a quadratic word equation with regular constraints. We provide an encoding of the effect of a simple loop of the counter systems in the existential theory of Presburger Arithmetic with divisibility (PAD). Since PAD is decidable (NP-hard and is in NEXP), we obtain a decision procedure for quadratic words equations with length constraints for which the associated counter system is flat (i.e., all nodes belong to at most one cycle). In particular, we show a decidability result (in fact, also an NP algorithm with a PAD oracle) for a recently proposed NP-complete fragment of word equations called regular-oriented word equations, when augmented with length constraints. We extend this decidability result (in fact, with a complexity upper bound of PSPACE with a PAD oracle) in the presence of regular constraints.Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibilityhttps://zbmath.org/1517.683202023-09-22T14:21:46.120933Z"Lin, Anthony W."https://zbmath.org/authors/?q=ai:lin.anthony-widjaja"Majumdar, Rupak"https://zbmath.org/authors/?q=ai:majumdar.rupakSummary: Word equations are a crucial element in the theoretical foundation of constraint solving over strings. A word equation relates two words over string variables and constants. Its solution amounts to a function mapping variables to constant strings that equate the left and right hand sides of the equation. While the problem of solving word equations is decidable, the decidability of the problem of solving a word equation with a length constraint (i.e., a constraint relating the lengths of words in the word equation) has remained a long-standing open problem. We focus on the subclass of quadratic word equations, i.e., in which each variable occurs at most twice. We first show that the length abstractions of solutions to quadratic word equations are in general not Presburger-definable. We then describe a class of counter systems with Presburger transition relations which capture the length abstraction of a quadratic word equation with regular constraints. We provide an encoding of the effect of a simple loop of the counter systems in the existential theory of Presburger Arithmetic with divisibility (PAD). Since PAD is decidable, we get a decision procedure for quadratic words equations with length constraints for which the associated counter system is \textit{flat} (i.e., all nodes belong to at most one cycle). In particular, we show a decidability result (in fact, also an NP algorithm with a PAD oracle) for a recently proposed NP-complete fragment of word equations called regular-oriented word equations, when augmented with length constraints. Decidability holds when the constraints are extended with regular constraints with a 1-weak control structure.
For the entire collection see [Zbl 1396.68018].Transition property for cube-free wordshttps://zbmath.org/1517.683212023-09-22T14:21:46.120933Z"Petrova, Elena A."https://zbmath.org/authors/?q=ai:petrova.elena-a"Shur, Arseny M."https://zbmath.org/authors/?q=ai:shur.arseny-mSummary: We study cube-free words over arbitrary non-unary finite alphabets and prove the following structural property: for every pair \((u, v)\) of \(d\)-ary cube-free words, if \(u\) can be infinitely extended to the right and \(v\) can be infinitely extended to the left respecting the cube-freeness property, then there exists a ``transition'' word \(w\) over the same alphabet such that \textit{uwv} is cube free. The crucial case is the case of the binary alphabet, analyzed in the central part of the paper.
The obtained ``transition property'', together with the developed technique, allowed us to solve cube-free versions of three old open problems by Restivo and Salemi. Besides, it has some further implications for combinatorics on words; e.g., it implies the existence of infinite cube-free words of very big subword (factor) complexity.
For the entire collection see [Zbl 1416.68013].Transition property for cube-free wordshttps://zbmath.org/1517.683222023-09-22T14:21:46.120933Z"Petrova, Elena A."https://zbmath.org/authors/?q=ai:petrova.elena-a"Shur, Arseny M."https://zbmath.org/authors/?q=ai:shur.arseny-mSummary: We study cube-free words over arbitrary non-unary finite alphabets and prove the following structural property: for every pair \((u,v)\) of \(d\)-ary cube-free words, if \(u\) can be infinitely extended to the right and \(v\) can be infinitely extended to the left respecting the cube-freeness property, then there exists a ``transition'' word \(w\) over the same alphabet such that \(uwv\) is cube free. The crucial case is the case of the binary alphabet, analyzed in the central part of the paper. The obtained ``transition property'', together with the developed technique, allowed us to solve cube-free versions of three old open problems by Restivo and Salemi. Besides, it has some further implications for combinatorics on words; e.g., it implies the existence of infinite cube-free words of very big subword (factor) complexity.Item enhanced graph collaborative network for collaborative filtering recommendationhttps://zbmath.org/1517.683322023-09-22T14:21:46.120933Z"Huang, Haichi"https://zbmath.org/authors/?q=ai:huang.haichi"Tian, Xuan"https://zbmath.org/authors/?q=ai:tian.xuan"Luo, Sisi"https://zbmath.org/authors/?q=ai:luo.sisi"Shi, Yanli"https://zbmath.org/authors/?q=ai:shi.yanliSummary: Learning vector embeddings of users and items is the core of modern recommender systems. Recently the collaborative filtering recommender systems based on graph convolutional networks, which integrates the bipartite graph of user-item interaction into the embedding process, has achieved significant success. However, such feature as item-item interaction sequence is neglected in the bipartite graph, which limits the ability to model sequential orders for embedding of items. In this work, we propose a novel item-item interaction sequential graph to globally aggregate the hidden interactions sequence among all items. It is derived from the order of all user-item interactions and can give a supplement for user-item interaction modeling in CF. We also propose an item enhanced graph collaborative network (IEGCN) to mix item-item sequences with user-item interactions for collaborative filtering. We performed experiments on three open datasets, and IEGCN shows substantial improvements in recall and normalized discounted cumulative gain when compared with existing mainstream models. Further analysis verifies the importance of item-item sequence graph to improve the recommendation effect.Structural iterative lexicographic autoencoded node representationhttps://zbmath.org/1517.683332023-09-22T14:21:46.120933Z"Joaristi, Mikel"https://zbmath.org/authors/?q=ai:joaristi.mikel"Serra, Edoardo"https://zbmath.org/authors/?q=ai:serra.edoardoSummary: Graph representation learning approaches are effective to automatically extract relevant hidden features from graphs. Previous related work in graph representation learning can be divided into connectivity and structural-based. Connectivity-based representation learning methods work on the assumption that neighboring nodes should have similar representations. While structural node representation learning assumes that nodes with the same structure should have identical representations; structural representation learning is suitable for node classification and regression tasks. Possible drawbacks of current structural node representation learning approaches are prohibitive execution time complexity and the inability to entirely preserve structural information. In this work, we propose SILA, a Structural Iterative Lexicographic Autoencoded approach for node representation learning. This new iterative approach presents a small number of iterations, and compared with the method presented in the literature, shows better performance in preserving structural information for both classification and regression tasks.Informative pseudo-labeling for graph neural networks with few labelshttps://zbmath.org/1517.683442023-09-22T14:21:46.120933Z"Li, Yayong"https://zbmath.org/authors/?q=ai:li.yayong"Yin, Jie"https://zbmath.org/authors/?q=ai:yin.jie"Chen, Ling"https://zbmath.org/authors/?q=ai:chen.lingSummary: Graph neural networks (GNNs) have achieved state-of-the-art results for semi-supervised node classification on graphs. Nevertheless, the challenge of how to effectively learn GNNs with very few labels is still under-explored. As one of the prevalent semi-supervised methods, pseudo-labeling has been proposed to explicitly address the label scarcity problem. It is the process of augmenting the training set with pseudo-labeled unlabeled nodes to retrain a model in a self-training cycle. However, the existing pseudo-labeling approaches often suffer from two major drawbacks. First, these methods conservatively expand the label set by selecting only high-confidence unlabeled nodes without assessing their informativeness. Second, these methods incorporate pseudo-labels to the same loss function with genuine labels, ignoring their distinct contributions to the classification task. In this paper, we propose a novel informative pseudo-labeling framework (InfoGNN) to facilitate learning of GNNs with very few labels. Our key idea is to pseudo-label the most informative nodes that can maximally represent the local neighborhoods via mutual information maximization. To mitigate the potential label noise and class-imbalance problem arising from pseudo-labeling, we also carefully devise a generalized cross entropy with a class-balanced regularization to incorporate pseudo-labels into model retraining. Extensive experiments on six real-world graph datasets validate that our proposed approach significantly outperforms state-of-the-art baselines and competitive self-supervised methods on graphs.Corrigendum to: ``Parallel algorithm for solving the graph isomorphism problem''https://zbmath.org/1517.684082023-09-22T14:21:46.120933Z"Vasilchikov, V. V."https://zbmath.org/authors/?q=ai:vasilchikov.vladimir-vasilevichFrom the text: In the article by the author [ibid. 27, No. 1, 86--94 (2020; Zbl 1513.68079)] there was a misprint in the layout. In the Table 1, in the last column of the row ``Degree of graph'' the value should be 3000 (instead of 300). The corrected ``Table 1'' is shown below. The editors apologise for the inconvenience.A self-stabilizing algorithm for maximal matching in link-register modelhttps://zbmath.org/1517.684092023-09-22T14:21:46.120933Z"Cohen, Johanne"https://zbmath.org/authors/?q=ai:cohen.johanne"Manoussakis, George"https://zbmath.org/authors/?q=ai:manoussakis.george"Pilard, Laurence"https://zbmath.org/authors/?q=ai:pilard.laurence"Sohier, Devan"https://zbmath.org/authors/?q=ai:sohier.devanSummary: This paper presents a new distributed self-stabilizing algorithm solving the maximal matching problem under the fair distributed daemon. This is the first maximal matching algorithm in the link-register model under read/write atomicity. This work is composed of two parts. As we cannot establish a move complexity analysis under the fair distributed daemon, we first design an algorithm \(\mathcal A_{1}\) under the unfair distributed daemon dealing with some relaxed constraints on the communication model. Second, we adapt \(\mathcal A_{1}\) so that it can handle the fair distributed daemon, leading to the \(\mathcal A_{2}\) algorithm. We prove that algorithm \(\mathcal A_1\) stabilizes in \(O(m\Delta)\) moves and algorithm \(\mathcal A_2\) in \(O(m\Delta)\) rounds, with \(\Delta\) the maximum degree and \(m\) the number of edges.
For the entire collection see [Zbl 1400.68027].Deterministic distributed dominating set approximation in the CONGEST modelhttps://zbmath.org/1517.684112023-09-22T14:21:46.120933Z"Deurer, Janosch"https://zbmath.org/authors/?q=ai:deurer.janosch"Kuhn, Fabian"https://zbmath.org/authors/?q=ai:kuhn.fabian"Maus, Yannic"https://zbmath.org/authors/?q=ai:maus.yannicBrief announcement: Local deal-agreement based monotonic distributed algorithms for load balancing in general graphshttps://zbmath.org/1517.684122023-09-22T14:21:46.120933Z"Dinitz, Yefim"https://zbmath.org/authors/?q=ai:dinitz.yefim"Dolev, Shlomi"https://zbmath.org/authors/?q=ai:dolev.shlomi"Kumar, Manish"https://zbmath.org/authors/?q=ai:kumar.manish.1|kumar.manish|kumar.manish.4|kumar.manish.2Summary: In computer networks, participants may cooperate in processing tasks, balancing working loads among them. The distributed load balancing problem is well-known. We present local algorithms solving it based on a short \textit{deal-agreement communication}. Unlike the previous algorithms, they converge \textit{monotonically}, always providing a better feasible state as the execution progresses. Our synchronous algorithms achieve \(\epsilon \)-Balanced state for the continuous setting in time \(O(n D \log (n K/\epsilon ))\) and 1-Balanced state for the discrete setting in time \(O(n D \log (n K/D) + n D^2)\), for \textit{general graphs} in the worst case, where \(n\) is the number of nodes, \(K\) is the initial discrepancy, and \(D\) is the graph diameter. We also suggest an \textit{asynchronous} load balancing algorithm solving the problem in time \(O(n K^2)\) for general graphs, and its \textit{self-stabilizing} version.
For the entire collection see [Zbl 1507.68029].Linear-time online algorithm inferring the shortest path from a walkhttps://zbmath.org/1517.684232023-09-22T14:21:46.120933Z"Narisada, Shintaro"https://zbmath.org/authors/?q=ai:narisada.shintaro"Hendrian, Diptarama"https://zbmath.org/authors/?q=ai:hendrian.diptarama"Yoshinaka, Ryo"https://zbmath.org/authors/?q=ai:yoshinaka.ryo"Shinohara, Ayumi"https://zbmath.org/authors/?q=ai:shinohara.ayumiSummary: We consider the problem of inferring an edge-labeled graph from the sequence of edge labels seen in a walk of that graph. It has been known that this problem is solvable in \(O(n \log n)\) time when the targets are path or cycle graphs. This paper presents an online algorithm for the problem of this restricted case that runs in \(O(n)\) time, based on Manacher's algorithm for computing all the maximal palindromes in a string.
For the entire collection see [Zbl 1398.68028].Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-orderhttps://zbmath.org/1517.684322023-09-22T14:21:46.120933Z"Daykin, Jacqueline W."https://zbmath.org/authors/?q=ai:daykin.jacqueline-w"Mhaskar, Neerja"https://zbmath.org/authors/?q=ai:mhaskar.neerja"Smyth, W. F."https://zbmath.org/authors/?q=ai:smyth.william-fSummary: \(V\)-order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs), a generalization of Lyndon words. The fundamental \(V\)-comparison of strings can be done in linear time and constant space. \(V\)-order has been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform (BWT). In line with the recent interest in the connection between suffix arrays and Lyndon factorization, in this paper we obtain similar results for the \(V\)-order factorization. Indeed, we show that the results describing the connection between suffix arrays and Lyndon factorization are matched by analogous \(V\)-order processing. We also describe a methodology for efficiently computing the FM-Index in \(V\)-order, as well as \(V\)-order substring pattern matching using backward search.Finding globally shortest paths through a sequence of adjacent triangles by the method of orienting curveshttps://zbmath.org/1517.901092023-09-22T14:21:46.120933Z"An, Phan Thanh"https://zbmath.org/authors/?q=ai:an.phan-thanh"Phu, Hoang Xuan"https://zbmath.org/authors/?q=ai:hoang-xuan-phu.Summary: In this paper, an exact algorithm based on the method of orienting curves is developed for solving the convex non-differentiable optimization problem on the closed unit cube in a finite dimensional space: finding the shortest path joining two points going through a sequence of adjacent triangles in 3D. As a result, the global solution of the problem is determined successively by some orienting curves and final curve, which can be exactly constructed with ruler and compass. A detailed numerical example is presented.Time-bounded influence diffusion with incentiveshttps://zbmath.org/1517.911742023-09-22T14:21:46.120933Z"Cordasco, Gennaro"https://zbmath.org/authors/?q=ai:cordasco.gennaro"Gargano, Luisa"https://zbmath.org/authors/?q=ai:gargano.luisa"Peters, Joseph G."https://zbmath.org/authors/?q=ai:peters.joseph-g"Rescigno, Adele A."https://zbmath.org/authors/?q=ai:rescigno.adele-anna"Vaccaro, Ugo"https://zbmath.org/authors/?q=ai:vaccaro.ugoSummary: A widely studied model of influence diffusion in social networks represents the network as a graph \(G=(V,E)\) with an influence threshold \(t(v)\) for each node. Initially the members of an initial set \(S\subseteq V\) are influenced. During each subsequent round, the set of influenced nodes is augmented by including every node \(v\) that has at least \(t\)(\(v\)) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total of the incentives required to ensure that the process completes within a given number of rounds. The problem is hard to approximate in general networks. We present polynomial-time algorithms for paths, trees, and complete networks.
For the entire collection see [Zbl 1400.68027].\(P_4\)-free partition and cover numbers \& applicationshttps://zbmath.org/1517.940662023-09-22T14:21:46.120933Z"Block, Alexander R."https://zbmath.org/authors/?q=ai:block.alexander-r"Brânzei, Simina"https://zbmath.org/authors/?q=ai:branzei.simina"Maji, Hemanta K."https://zbmath.org/authors/?q=ai:maji.hemanta-k"Mehta, Himanshi"https://zbmath.org/authors/?q=ai:mehta.himanshi"Mukherjee, Tamalika"https://zbmath.org/authors/?q=ai:mukherjee.tamalika"Nguyen, Hai H."https://zbmath.org/authors/?q=ai:nguyen.hai-hSummary: \(P_4\)-free graphs also known as cographs, complement-reducible graphs, or hereditary Dacey graphs have been well studied in graph theory. Motivated by computer science and information theory applications, our work encodes (flat) joint probability distributions and Boolean functions as bipartite graphs and studies bipartite \(P_4\)-free graphs. For these applications, the graph properties of edge partitioning and covering a bipartite graph using the minimum number of these graphs are particularly relevant. Previously, such graph properties have appeared in leakage-resilient cryptography and (variants of) coloring problems. Interestingly, our covering problem is closely related to the well-studied problem of product (a.k.a., Prague) dimension of loopless undirected graphs, which allows us to employ algebraic lower-bounding techniques for the product/Prague dimension. We prove that computing these numbers is NP-complete, even for bipartite graphs. We establish a connection to the (unsolved) Zarankiewicz problem to show that there are bipartite graphs with size-\(N\) partite sets such that these numbers are at least \(\varepsilon\cdot N^{1-2 \varepsilon}\), for \(\varepsilon\in \{1/3,1/4,1/5,\dots\}\). Finally, we accurately estimate these numbers for bipartite graphs encoding well-studied Boolean functions from circuit complexity, such as set intersection, set disjointness, and inequality. For applications in information theory and communication \& cryptographic complexity, we consider a system where a setup samples from a (flat) joint distribution and gives the participants, Alice and Bob, their portion from this joint sample. Alice and Bob's objective is to non-interactively establish a shared key and extract the left-over entropy from their portion of the samples as independent private randomness. A genie, who observes the joint sample, provides appropriate assistance to help Alice and Bob with their objective. Lower bounds to the minimum size of the genie's assistance translate into communication and cryptographic lower bounds. We show that (the \(\log_2\) of) the \(P_4\)-free partition number of a graph encoding the joint distribution that the setup uses is equivalent to the size of the genie's assistance. Consequently, the joint distributions corresponding to the bipartite graphs constructed above with high \(P_4\)-free partition numbers correspond to joint distributions requiring more assistance from the genie. As a representative application in non-deterministic communication complexity, we study the communication complexity of nondeterministic protocols augmented by access to the equality oracle at the output. We show that (the \(\log_2\) of) the \(P_4\)-free cover number of the bipartite graph encoding a Boolean function \(f\) is equivalent to the minimum size of the nondeterministic input required by the parties (referred to as the communication complexity of \(f\) in this model). Consequently, the functions corresponding to the bipartite graphs with high \(P_4\)-free cover numbers have high communication complexity. Furthermore, there are functions with communication complexity close to the naïve protocol where the nondeterministic input reveals a party's input. Finally, the access to the equality oracle reduces the communication complexity of computing set disjointness by a constant factor in contrast to the model where parties do not have access to the equality oracle. To compute the inequality function, we show an exponential reduction in the communication complexity, and this bound is optimal. On the other hand, access to the equality oracle is (nearly) useless for computing set intersection.
For the entire collection see [Zbl 1465.94005].