Search

In this paper, we study the problem of gossiping with interference constraint in radio ring networks. Gossiping (or total exchange information) is a protocol where each node in the network has a message and is expected to distribute its own message to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and algorithms that attain this makespan. We focus on the case where the transmission network is a ring network. We consider synchronous protocols where it takes one unit of time (step) to transmit a unit-length message. During one step, a node receives at most one message only through one of its two neighbors. We also suppose that, during one step, a node cannot be both a sender and a receiver (half duplex model). Moreover communication is subject to interference constraints. We use a primary node interference model where, if a node receives a message from one of its neighbors, its other neighbor cannot send at the same time. With these assumptions we completely solve the problem for ring networks. We first show lower bounds and then give gossiping algorithms which meet these lower bounds and so are optimal. The number of rounds depends on the congruences of n modulo 12. [ABSTRACT FROM AUTHOR]

The (bitwise) complement x of a binary word x is obtained by changing each 0 in x to 1 and vice versa. An antisquare is a nonempty word of the form x x. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is (5 +√5)/2. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number. We say a binary word is good if the only antisquares it contains are 01 and 10. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length n and determine the repetition threshold between polynomial and exponential growth for the number of good words. [ABSTRACT FROM AUTHOR]

We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiod and having the smallest possible critical exponent. Finally, we consider the problem of determining whether a finite word is pseudoperiodic of a given size, and show that it is NP-complete. [ABSTRACT FROM AUTHOR]

Mixed graphs have both directed and undirected edges. We consider mixed graphs that are regular in both directed and undirected degree and with given girth. Araujo-Pardo, Hern'andez-Cruz, andMontellano-Ballesteros recently established a lower bound for regular mixed graphs with directed degree one that generalizes the Moore bound. In this paper we show that, in at least one non-trivial case, their bound can be achieved. For a few other specific values of direct degree, undirected degree and girth we are able to identify graphs (mixed cages) of minimum possible order. We also obtain some fairly tight bounds for a few other cases. [ABSTRACT FROM AUTHOR]

A distributed graph algorithm is an algorithm where every node determines its output by inspecting its local neighborhood. As distributed environments are subject to faults, an important issue is to be able to check that the output is correct, or in general that the network is in proper configuration with respect to some predicate. One would like this checking to be very local, to avoid using too much time. Unfortunately, most predicates cannot be checked this way, and that is where certification comes into play. Local certification (also known as proof-labeling schemes, locally checkable proofs, or distributed verification) consists in assigning labels to the nodes, that certify that the configuration is correct. In this paper, we present several different perspectives for studying local certification: as a part of self-stabilizing algorithms, as a labeling problem, or as a non-deterministic distributed decision. This paper is an introduction to the domain of local certification, giving an overview of the history, the techniques and the current research directions. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V,E) with a nonnegative edge length function and an integer p, 0 < p < |V |, the p-centdian problem is to find p vertices (called the centdian set) of V such that the eccentricity plus median-distance is minimized, in which the eccentricity is the maximum (length) distance of all vertices to their nearest centdian set and the median-distance is the total (length) distance of all vertices to their nearest centdian set. The eccentricity plus median-distance is called the centdian-distance. The purpose of the p-centdian problem is to find p open facilities (servers) which satisfy the quality-of-service of the minimum total distance (median-distance) and the maximum distance (eccentricity) to their service customers, simultaneously. If we converse the two criteria, that is given the bound of the centdian-distance and the objective function is to minimize the cardinality of the centdian set, this problem is called the converse centdian problem. In this paper, we prove the p-centdian problem is NP-Complete. Then we design the first non-trivial brute force exact algorithms for the p-centdian problem and the converse centdian problem, respectively. Finally, we design two approximation algorithms for both problems. [ABSTRACT FROM AUTHOR]

We study the following problem. Given a multiset M of non-negative integers, decide whether there exist and, in the positive case, compute two non-trivial multisets whose Minkowski sum is equal to M. The Minkowski sum of two multisets A and B is a multiset containing all possible sums of any element of A and any element of B. This problem was proved to be NP-complete when multisets are replaced by sets. This version of the problem is strictly related to the factorization of boolean polynomials that turns out to be NP-complete as well. When multisets are considered, the problem is equivalent to the factorization of polynomials with non-negative integer coefficients. The computational complexity of both these problems is still unknown. The main contribution of this paper is a heuristic technique for decomposing multisets of non-negative integers. Experimental results show that our heuristic decomposes multisets of hundreds of elements within seconds, independently of the magnitude of numbers belonging to the multisets. Our heuristic can also be used for factoring polynomials in N[x]. We show that, when the degree of the polynomials gets larger, our technique is much faster than the state-of-the-art algorithms implemented in commercial software like Mathematica and MatLab. [ABSTRACT FROM AUTHOR]

When can we compute the diameter of a graph in quasi linear time? We address this question for the class of split graphs, that we observe to be the hardest instances for deciding whether the diameter is at most two. We stress that although the diameter of a non-complete split graph can only be either 2 or 3, under the Strong ExponentialTime Hypothesis (SETH) we cannot compute the diameter of an n-vertex m-edge split graph in less than quadratic time – in the size n + m of the input. Therefore it is worth to study the complexity of diameter computation on subclasses of split graphs, in order to better understand the complexity border. Specifically, we consider the split graphs with bounded clique-interval number and their complements, with the former being a natural variation of the concept of interval number for split graphs that we introduce in this paper. We first discuss the relations between the clique-interval number and other graph invariants such as the classic interval number of graphs, the treewidth, the VC-dimension and the stabbing number of a related hypergraph. Then, in part based on these above relations, we almost completely settle the complexity of diameter computation on these subclasses of split graphs: • For the k-clique-interval split graphs, we can compute their diameter in truly subquadratic time if k = O(1), and even in quasi linear time if k = o(log n) and in addition a corresponding ordering of the vertices in the clique is given. However, under SETH this cannot be done in truly subquadratic time for any k = ω(log n). • For the complements of k-clique-interval split graphs, we can compute their diameter in truly subquadratic time if k = O(1), and even in time O(km) if a corresponding ordering of the vertices in the stable set is given. Again this latter result is optimal under SETH up to polylogarithmic factors. Our findings raise the question whether a k-clique interval ordering can always be computed in quasi linear time. We prove that it is the case for k = 1 and for some subclasses such as bounded-treewidth split graphs, threshold graphs and comparability split graphs. Finally, we prove that some important subclasses of split graphs – including the ones mentioned above – have a bounded clique-interval number. [ABSTRACT FROM AUTHOR]

An outer-1-planar graph is a graph admitting a drawing in the plane so that all vertices appear in the outer region of the drawing and every edge crosses at most one other edge. This paper establishes the local structure of outer-1- planar graphs by proving that each outer-1-planar graph contains one of the seventeen fixed configurations, and the list of those configurations is minimal in the sense that for each fixed configuration there exist outer-1-planar graphs containing this configuration that do not contain any of another sixteen configurations. There are two interesting applications of this structural theorem. First of all, we conclude that every (resp. maximal) outer-1-planar graph of minimum degree at least 2 has an edge with the sum of the degrees of its two end-vertices being at most 9 (resp. 7), and this upper bound is sharp. On the other hand, we show that the list 3-dynamic chromatic number of every outer-1-planar graph is at most 6, and this upper bound is best possible. [ABSTRACT FROM AUTHOR]

Let D be a strong balanced digraph on 2a vertices. Adamus et al. have proved that D is hamiltonian if d(u)+d(v) ≥ 3a whenever uv ∈ A(D) and vu ∈ A(D). The lower bound 3a is tight. In this paper, we shall show that the extremal digraph on this condition is two classes of digraphs that can be clearly characterized. Moreover, we also show that if d(u) + d(v) ≥ 3a − 1 whenever uv ∈ A(D) and vu ∈ A(D), then D is traceable. The lower bound 3a − 1 is tight. [ABSTRACT FROM AUTHOR]

The Hausdorff distance is a relatively new measure of similarity of graphs. The notion of the Hausdorff distance considers a special kind of a common subgraph of the compared graphs and depends on the structural properties outside of the common subgraph. There was no known efficient algorithm for the problem of determining the Hausdorff distance between two trees, and in this paper we present a polynomial-time algorithm for it. The algorithm is recursive and it utilizes the divide and conquer technique. As a subtask it also uses the procedure that is based on the well known graph algorithm of finding the maximum bipartite matching. [ABSTRACT FROM AUTHOR]

Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on n vertices with an O(n4) time delay. In this paper, we improve their algorithm and achieve O(n3 log n) time delay. We also extend the catalog of these graphs providing a list of all non-isomorphic interval graphs for all n up to 15. [ABSTRACT FROM AUTHOR]

In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function. Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. In particular, it is useful to find discretization orders that minimize an indicator of the size of the search tree. Our stepwise linear cost function generalizes this situation and allows to discriminate the vertices into three categories depending on the number of adjacent predecessors of each vertex in the order and on two parameters K and U. We provide a complete study of NP-completeness for fixed values of K and U. Our main result is that the problem is NP-complete in general for all values of K and U such that U ≥K + 1 and U ≥2. A consequence of this result is that the minimization of vertices with exactly K adjacent predecessors in a discretization order is also NP-complete. [ABSTRACT FROM AUTHOR]

In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend the graph against an infinite sequence of attacks. In this paper, we continue the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as 2×n, 3×n, 4×n, and 5×n grids, and recently it was proven in [Lamprou et al., CIAC 2017, 393-404] that the eternal domination number of these grids in general is within O(m+n) of their domination number which lower bounds the eternal domination number. Recently, Finbow et al. proved that the eternal domination number of strong grids is upper bounded by mn6+O(m+n). We adapt the techniques of [Lamprou et al., CIAC 2017, 393-404] to prove that the eternal domination number of strong grids is upper bounded by mn7+O(m+n). While this does not improve upon a recently announced bound of ⌈m3⌉⌈n3⌉+O(mn--√) [Mc Inerney, Nisse, Pérennes, CIAC 2019] in the general case, we show that our bound is an improvement in the case where the smaller of the two dimensions is at most 6179. [ABSTRACT FROM AUTHOR]

It is commonly believed that real networks are scale-free and the fraction of nodes P(k) with degree k satisfies the power-law P(k) / k-γ for k > kmin > 0. Preferential attachment is the mechanism that has been considered responsible for such organization of these networks. In many real networks, degree distribution before the kmin varies very slowly to the extent of being uniform as compared to the degree distribution for k > kmin. In this paper, we propose a model that describes this particular degree distribution for the whole range of k > 0. We adopt a two step approach. In the first step, at every time stamp we add a new node to the network and attach it to an existing node using preferential attachment method. In the second step, we add edges between existing pairs of nodes with the node selection based on the uniform probability distribution. Our approach generates weakly scale-free networks that closely follow the degree distribution of real-world networks. We perform a comprehensive mathematical analysis of the model in the discrete domain and compare the degree distribution generated by this model with that of real-world networks. [ABSTRACT FROM AUTHOR]

A formal inverse of a given automatic sequence (the sequence of coefficients of the composition inverse of its associated formal power series) is also automatic. The comparison of properties of the original sequence and its formal inverse is an interesting problem. Such an analysis has been done before for the Thue-Morse sequence. In this paper, we describe arithmetic properties of formal inverses of the generalized Thue-Morse sequences and formal inverses of two modifications of the Rudin-Shapiro sequence. In each case, we give the recurrence relations and the automaton, then we analyze the lengths of factors consisting of identical letters as well as the frequencies of letters. We also compare the obtained results with the original sequences. [ABSTRACT FROM AUTHOR]

Define a sequence of elements from a partially ordered set to be heapable if it can be successively inserted as the leaves of a binary tree, not necessarily complete, such that children nodes are always greater or equal than parent nodes. This is a natural binary analog of the notion of a chain in a poset and an easy extension of a definition for integers due to Byers et al. (2011). A set of elements is called heapable if some permutation of its elements is. We investigate the partitioning of sequences from a poset into a minimal number of heapable subsequences. We give an extension of Fulkerson's proof of Dilworth's theorem to decomposition into heapable subsequences which yields as a byproduct a flow-based algorithm for computing such a minimal decomposition. On the other hand, for sets and sequences of intervals and for trapezoid partial orders we prove that such minimal decompositions can be computed via simple greedy-type algorithms. Second, while the complexity of computing a maximal heapable subsequence of integers is still open, we show that this problem has a polynomial time algorithm for sequences of intervals. The paper concludes with a couple of open problems related to the analog of the Ulam-Hammersley problem for sets and sequences of random intervals. [ABSTRACT FROM AUTHOR]

The enumeration of inversion sequences avoiding a single pattern was initiated by Corteel, Martinez, Savage and Weselcouch, and Mansour and Shattuck, independently. Their work has sparked various investigations of generalized patterns in inversion sequences, including patterns of relation triples by Martinez and Savage, consecutive patterns by Auli and Elizalde, and vincular patterns by Lin and Yan. In this paper, we carried out the systematic study of inversion sequences avoiding two patterns of length 3. Our enumerative results establish further connections to the OEIS sequences and some classical combinatorial objects, such as restricted permutations, weighted ordered trees and set partitions. Since patterns of relation triples are some special multiple patterns of length 3, our results complement the work by Martinez and Savage. In particular, one of their conjectures regarding the enumeration of (021, 120)- avoiding inversion sequences is solved. [ABSTRACT FROM AUTHOR]

Let Sa;b denote the sequence of leading digits of an in base b. It is well known that if a is not a rational power of b, then the sequence Sa;b satisfies Benford's Law; that is, digit d occurs in Sa;b with frequency logb(1 + 1/d), for d = 1; 2; : : : ; b-1. In this paper, we investigate the complexity of such sequences. We focus mainly on the block complexity, pa;b(n), defined as the number of distinct blocks of length n appearing in Sa;b. In our main result we determine pa;b(n) for all squarefree bases b ≥ 5 and all rational numbers a > 0 that are not integral powers of b. In particular, we show that, for all such pairs (a; b), the complexity function pa;b(n) is an affine function, i.e., of the form pa;b(n) = ca;bn+da;b for all n ≥ 1, with coefficients ca;b ≥ 1 and da;b ≥ 0, given explicitly in terms of a and b. We also show that the requirement that b be squarefree cannot be dropped: If b is not squarefree, then there exist integers a with 1 < a < b for which pa;b(n) is not of the above form. We use this result to obtain sharp upper and lower bounds for pa;b(n) and to determine the asymptotic behavior of this function as b ! 1 through squarefree values. We also consider the question which affine functions p(n) = cn + d arise as the complexity function pa;b(n) of some leading digit sequence Sa;b. We conclude with a discussion of other complexity measures for the sequences Sa;b and some open problems. [ABSTRACT FROM AUTHOR]

Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph G is a graph that admits a representation where its vertices correspond to paths in a grid Q, such that two vertices of G are adjacent if and only if their corresponding paths in Q have a common edge. If the paths in the representation have at most k bends, we say that it is a Bk-EPG representation. A collection C of sets satisfies the Helly property when every sub-collection of C that is pairwise intersecting has at least one common element. In this paper, we show that given a graph G and an integer k, the problem of determining whether G admits a Bk-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-Bk-EPG representation, is in NP, for every k bounded by a polynomial function of jV (G)j. Moreover, we show that the problem of recognizing Helly-B1-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs. [ABSTRACT FROM AUTHOR]

It has been shown by Bokal et al. that deciding 2-colourability of digraphs is an NP-complete problem. This result was later on extended by Feder et al. to prove that deciding whether a digraph has a circular p-colouring is NPcomplete for all rational p > 1. In this paper, we consider the complexity of corresponding decision problems for related notions of fractional colourings for digraphs and graphs, including the star dichromatic number, the fractional dichromatic number and the circular vertex arboricity. We prove the following results: • Deciding if the star dichromatic number of a digraph is at most p is NP-complete for every rational p > 1. • Deciding if the fractional dichromatic number of a digraph is at most p is NP-complete for every p > 1; p 6= 2. • Deciding if the circular vertex arboricity of a graph is at most p is NP-complete for every rational p > 1. To show these results, different techniques are required in each case. In order to prove the first result, we relate the star dichromatic number to a new notion of homomorphisms between digraphs, called circular homomorphisms, which might be of independent interest. We provide a classification of the computational complexities of the corresponding homomorphism colouring problems similar to the one derived by Feder et al. for acyclic homomorphisms. [ABSTRACT FROM AUTHOR]

Let P be a set of n≥4 points in general position in the plane. Consider all the closed straight line segments with both endpoints in P. Suppose that these segments are colored with the rule that disjoint segments receive different colors. In this paper we show that if P is the point configuration known as the double chain, with k points in the upper convex chain and l≥k points in the lower convex chain, then k+l-√2l+1/4-1/2˩ colors are needed and that this number is sufficient. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to study a statistic that is used to compare the similarity between two strings, which is first introduced by Michael Steele in 1982. It was proposed as an alternative to the length of the longest common subsequences, for which the variance problem is still open. Our results include moment asymptotics and distributional asymptotics for Steele's statistic and a variation of it in random words. [ABSTRACT FROM AUTHOR]

Let G = (X, Y ;E) be a bipartite graph, where X and Y are color classes and E is the set of edges of G. Lov´asz and Plummer asked whether one can decide in polynomial time that a given bipartite graph G = (X, Y ;E) admits a 1-anti-factor, that is subset F of E such that dF (v) = 1 for all v ∈ X and dF (v) 6= 1 for all v ∈ Y . Cornuéjols answered this question in the affirmative. Yu and Liu asked whether, for a given integer k ≥ 3, every k-regular bipartite graph contains a 1-anti-factor. This paper answers this question in the affirmative. [ABSTRACT FROM AUTHOR]