Search

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

We study a security game over a network played between a defender and kattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing defense-optimal networks which allow for the best equilibrium defense ratio; this is the ratio of k over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for λ constantly close to 1 or n. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any λ ; this is the worst equilibrium defense ratio over all graphs. [ABSTRACT FROM AUTHOR]

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. Sampled string matching is an efficient approach recently introduced in order to overcome the prohibitive space requirements of an index construction, on the one hand, and drastically reduce searching time for the online solutions, on the other hand. In this paper we present a new algorithm for the sampled string matching problem, based on a characters distance sampling approach. The main idea is to sample the distances between consecutive occurrences of a given pivot character and then to search online the sampled data for any occurrence of the sampled pattern, before verifying the original text. From a theoretical point of view we prove that, under suitable conditions, our solution can achieve both linear worst-case time complexity and optimal average-time complexity. From a practical point of view it turns out that our solution shows a sub-linear behaviour in practice and speeds up online searching by a factor of up to 9, using limited additional space whose amount goes from 11 to 2.8% of the text size, with a gain up to 50% if compared with previous solutions. [ABSTRACT FROM AUTHOR]

In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time n O (k) . This improves the naive algorithm that runs in time n O (k 2) by Espelage et al. (Graph-theoretic concepts in computer science, vol 2204. Springer, Berlin, 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time n o (k) (Fomin et al. in SIAM J Comput 43:1541–1563, 2014). We present a technique of representative sets using two-edge colored multigraphs on k vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on k vertices with at most n edges. [ABSTRACT FROM AUTHOR]

Let B = (X , Y , E) be a bipartite graph. A half-square of B has one color class of B as vertex set, say X; two vertices are adjacent whenever they have a common neighbor in Y. Every planar graph is a half-square of a planar bipartite graph, namely of its subdivision. Until recently, only half-squares of planar bipartite graphs, also known as map graphs (Chen et al., in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, STOC '98, pp 514–523. 10.1145/276698.276865, 1998; J ACM 49(2):127–138. 10.1145/506147.506148, 2002), have been investigated, and the most discussed problem is whether it is possible to recognize these graphs faster and simpler than Thorup's O (n 120) -time algorithm (Thorup, in: Proceedings of the 39th IEEE symposium on foundations of computer science (FOCS), pp 396–405. 10.1109/SFCS.1998.743490, 1998). In this paper, we identify the first hardness case, namely that deciding if a graph is a half-square of a balanced bisplit graph is NP-complete. (Balanced bisplit graphs form a proper subclass of star convex bipartite graphs). For classical subclasses of tree convex bipartite graphs such as biconvex, convex, and chordal bipartite graphs, we give good structural characterizations of their half-squares that imply efficient recognition algorithms. As a by-product, we obtain new characterizations of unit interval graphs, interval graphs, and of strongly chordal graphs in terms of half-squares of biconvex bipartite, convex bipartite, and of chordal bipartite graphs, respectively. Good characterizations of half-squares of star convex and star biconvex bipartite graphs are also given, giving linear-time recognition algorithms for these half-squares. [ABSTRACT FROM AUTHOR]

Research on graph searching has recently gained interest in computer science, mathematics, and physics. This paper studies fast searching of a fugitive in a graph, a model that was introduced by Dyer et al. (in: Fleischer, Xu (eds.) Algorithmic aspects in information and management, Springer, New York, 2008). We provide lower bounds and upper bounds on the fast search number (i.e., the minimum number of searchers required for capturing the fugitive) of complete k-partite graphs. We also investigate some special classes of complete k-partite graphs, such as complete bipartite graphs and complete split graphs. We solve the open problem of determining the fast search number of complete bipartite graphs, and present upper and lower bounds on the fast search number of complete split graphs. [ABSTRACT FROM AUTHOR]

The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2 nodes under the unit-cost RAM model with a fixed word size w. It is based on the idea of partitioning T into a set of linked small tries, each of which can be maintained efficiently. Our method is not only space-efficient, but also allows the longest common prefix between any query pattern P and the strings currently stored in T to be computed in o(| P|) time for small alphabets, and allows any leaf to be inserted into or deleted from T in o(log| T|) time. To demonstrate the usefulness of our new data structure, we apply it to LZ-compression. Significantly, we obtain the first algorithm for generating the lz78 encoding of a given string of length n over an alphabet of size σ in sublinear ( o( n)) time and sublinear ( o( nlog σ) bits) working space for small alphabets ( $\sigma= 2^{o(\log n \frac{\log\log\log n}{(\log\log n)^{2}})}$). Moreover, the working space for our new algorithm is asymptotically less than or equal to the space for storing the output compressed text, regardless of the alphabet size. [ABSTRACT FROM AUTHOR]