Search

In this paper we consider the problem of maximizing a non-monotone and non-negative DR-submodular function on a bounded integer lattice [ B → ] = { (x 1 , ... , x n) ∈ Z + n : 0 ≤ x k ≤ B k , ∀ 1 ≤ k ≤ n } without any constraint, where B → = (B 1 , ... , B n) ∈ Z + n. We design an algorithm for the problem and measure its performance by its approximation ratio and the number of value oracle queries it needs, where the latter one is the dominating term in the running time of an algorithm. It has been showed that, for the problem considered, any algorithm achieving an approximation ratio greater than 1 2 requires an exponential number of value oracle queries. In the literature there are two algorithms that reach 1 2 approximation guarantee. The first algorithm needs O (n | | B | | ∞) oracle queries. The second one reduces its number of oracle queries to O (n max ⁡ { 1 , log ⁡ | | B → | | ∞ }) but it needs large storage. In this paper we present a randomized approximation algorithm that has an approximation guarantee of 1 2 , calls O (n max ⁡ { 1 , log ⁡ | | B → | | ∞ }) oracle queries and does not need large storage, improving the results of the literature. [ABSTRACT FROM AUTHOR]

The cohesive subgraph k-core is a maximal connected subgraph with the minimum degree δ ≥ k of a simple graph, where integer k ≥ 0. Define the core number of a vertex w as the maximum k such that w is contained in a k -core. The core decomposition problem which is calculating the core numbers of all vertices in static graphs, and the core maintenance problem which is updating the core numbers in dynamic graphs are our main concern. Although, core numbers can be updated by the core decomposition algorithms, only a small part of vertices' core numbers have changed after the change of a graph. Thus, it is necessary to update core numbers locally to reduce the cost. In this paper, we study the core maintenance problem on edge-weighted graphs by using the vertex sequence k-order which is ordered by the order that the core decomposition algorithm removes vertices. We design the core maintenance algorithms for inserting one edge at a time and the method of updating the k -order, which reduce the searching range and the time cost evidently. For the removing case, we use the existing subcore algorithm to do the core maintenance and modify it with the method of updating k -order we design. Finally, we do extensive experiments to evaluate the effectiveness and the efficiency of our algorithms, which shows that the order based algorithm has a better performance than the existing for the core maintenance on edge-weighted graphs. • We solve the core maintenance problem on edge-weighted graphs with a tool named weighted k -order. • The weighted k -order, a vertex sequence, is defined on edge-weighted graphs for the first time. • We give the properties of vertices whose core numbers increase on the k-order for inserting case on edge-weighted graphs. • The order based core maintenance algorithm for inserting case on edge-weighted graphs is given, which is the best. • We give the methods to update the k-order after inserting or removing one edge for the next core maintenance. [ABSTRACT FROM AUTHOR]

In the l -Path Vertex Cover problem (resp., the l -Component Order Connectivity problem) the input is an undirected graph G and an integer k. The goal is to decide whether there is a set of vertices of size at most k whose deletion from G results in a graph that does not contain a path with l vertices (resp., does not contain a connected component with at least l vertices). In this paper we give a parameterized algorithm for l -Path Vertex Cover when l = 5 , 6 , 7 , whose running times are O ⁎ (3.945 k) , O ⁎ (4.947 k) , and O ⁎ (5.951 k) , respectively. We also give an algorithm for l -Component Order Connectivity whose running time is O ⁎ ((l − 1 − ϵ l) k) for every l ≥ 4 , where ϵ l > 0 for every l. [ABSTRACT FROM AUTHOR]

The study of non-submodular maximization on the integer lattice is an important extension of submodular optimization. In this paper, streaming algorithms for maximizing non-negative monotone non-submodular functions with knapsack constraint on integer lattice are considered. We first design a two-pass StreamingKnapsack algorithm combining with BinarySearch as a subroutine for this problem. By introducing the DR ratio γ and the weak DR ratio γ w of the non-submodular objective function, we obtain that the approximation ratio is min ⁡ { γ 2 (1 − ε) / 2 γ + 1 , 1 − 1 / γ w 2 γ − ε } , the total memory complexity is O (K log ⁡ K / ε) , and the total query complexity for each element is O (log ⁡ K log ⁡ (K / ε 2) / ε). Then, we design a one-pass streaming algorithm by dynamically updating the maximal function value among unit vectors along with the currently arriving element. Finally, in order to decrease the memory complexity, we design an improved StreamingKnapsack algorithm and reduce the memory complexity to O (K / ε 2). • A two-pass streaming algorithm is proposed for maximizing monotone non-submodular functions with knapsack constraint on integer lattice. • By introducing DR ratio γ d (weak DR ratio γ w) we obtain the approximation ratio as min ⁡ { γ 2 (1 − ε) / 2 γ + 1 , 1 − 1 / γ w 2 γ − ε } with memory O (K log ⁡ K / ε). • A one-pass streaming algorithm is designed by dynamically updating the maximal function value among unit vectors. • We design an improve StreamingKnapsack algorithm and reduce the memory complexity to O (K / ε 2). [ABSTRACT FROM AUTHOR]

In this paper we consider doubly symmetric Dyck words , i.e. Dyck words which are fixed by two symmetry operations α and β introduced in [1]. We study combinatorial properties of doubly symmetric Dyck words, leading to the definition of two recursive algorithms to build these words. As a consequence we have a representation of doubly symmetric Dyck words as vectors of integers, called track vectors. Finally, we show some bijections between a subfamily of doubly symmetric Dyck words and a subfamily of integer partitions. The computation of the sequence f n of doubly symmetric Dyck words of semi-length n shows surprising properties giving rise to some conjectures. [ABSTRACT FROM AUTHOR]

An ortho-polygon visibility representation (OPVR) of an embedded graph G is an embedding-preserving drawing that maps each vertex of G to a distinct orthogonal polygon and each edge of G to a vertical or horizontal visibility between its end-vertices. An OPVR Γ has vertex complexity k if every polygon of Γ has at most k reflex corners. A 1-plane graph is an embedded graph such that each edge is crossed at most once. It is known that 3-connected 1-plane graphs admit an OPVR with vertex complexity at most 12, while vertex complexity at least 2 may be required in some cases. In this paper, we reduce this gap by showing that vertex complexity 5 is always sufficient, while vertex complexity 4 may be sometimes required. These results are based on the study of the combinatorial properties of the B-, T-, and W-configurations in 3-connected 1-plane graphs. An implication of the upper bound is the existence of a O ˜ (n 10 7 ) -time drawing algorithm that computes an OPVR of an n -vertex 3-connected 1-plane graph on an integer grid of size O (n) × O (n) and with vertex complexity at most 5. [ABSTRACT FROM AUTHOR]

Given a sequence of n numbers and two positive integers L and U with L ≤ U , the maximum sum segment problem is to find a segment of the sequence with length between L and U such that the sum of numbers in this segment is maximized. In this paper, we introduce the concept of uncertainty into the maximum sum segment problem, where each of the n numbers of the sequence is not given as an exact value but as an interval characterizing the possible range of its value. In such a sequence with uncertainty, we are interested in segments that have potentiality to be maximum sum segments. A segment is a potential maximum sum segment if there exists a possible assignment scenario of the uncertain numbers such that the segment has maximum sum under this assignment. We define the maximum sum segment with uncertainty (MSSU) problem, which consists of two sub-problems: (1) reporting all potential maximum sum segments; and (2) counting the total number of those segments. For the case that L = 1 and U = n , we propose an O (n + K) -time algorithm for the reporting problem and an O (n) -time algorithm for the counting problem, where K is the number of potential maximum sum segments. For general L and U , we give an O (n (U − L)) -time algorithm for either the reporting or the counting problem. Note that we assume the word-RAM model of computation. [ABSTRACT FROM AUTHOR]

The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p -Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p , and study its computational complexity. [ABSTRACT FROM AUTHOR]

In this paper we consider two problems concerning string factorisation. Specifically given a string w and an integer k find a factorisation of w where each factor has length bounded by k and has the minimum (the F-Min-D problem) or the maximum (the F-Max-D problem) number of different factors. The F-Min-D has been proved to be NP-hard even if k = 2 in [9] and for this case we provide a 3/2-approximation algorithm. The F-Max-D problem, up to our knowledge has not been considered in the literature. We show that this problem is NP-hard for any k ≥ 3. In view of this we propose a 2-approximation algorithm (for any k) and an FPT algorithm w.r.t. parameter max ⁡ { k , | Σ | }. [ABSTRACT FROM AUTHOR]

In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A streamed graph is a stream of edges e 1 , e 2 , ... , e m on a vertex set V. A streamed graph is ω-stream planar with respect to a positive integer window size ω if there exists a sequence of planar topological drawings Γ i of the graphs G i = (V , { e j | i ≤ j < i + ω }) such that the common graph G ∩ i = G i ∩ G i + 1 is drawn the same in Γ i and in Γ i + 1 , for 1 ≤ i ≤ m − ω. The Stream Planarity Problem with window size ω asks whether a given streamed graph is ω -stream planar. We also consider a generalization, where there is an additional backbone graph whose edges have to be present during each time step. These problems are related to several well-studied planarity problems. We show that the Stream Planarity Problem is NP -complete even when the window size is a constant and that the variant with a backbone graph is NP -complete for all ω ≥ 2. On the positive side, we provide O (n + ω m) -time algorithms for (i) the case ω = 1 and (ii) all values of ω provided the backbone graph is 2-connected. Our results improve on the Hanani-Tutte-style algorithm proposed by Schaefer [GD'14] for ω = 1 , which runs in O ((n m) 3) time. [ABSTRACT FROM AUTHOR]

A string X = X [ 1.. n ] , n > 1 , is said to be closed if it has a nonempty proper prefix that is also a suffix, but that otherwise occurs nowhere else in X ; for n = 1 , every X is closed. Closed strings were introduced by Fici in [1] as objects of combinatorial interest. Recently Badkobeh et al. [2] described a variety of algorithms to factor a given string into closed factors. In particular, they studied the Longest Closed Factorization (LCF) problem, which greedily computes the decomposition X = X 1 X 2 ⋯ X k , where X 1 is the longest closed prefix of X , X 2 the longest closed prefix of X with prefix X 1 removed, and so on. In this paper we present an O (log ⁡ n) amortized per character algorithm to compute LCF on-line, where n is the length of the string. We also introduce the Minimum Closed Factorization (MCF) problem, which identifies the minimum number of closed factors that cover X. We first describe an off-line O (n log 2 ⁡ n) -time algorithm to compute M C F (X) , then we present an on-line algorithm for the same problem. In fact, we show that M C F (X) can be computed in O (L log ⁡ n) time from M C F (X ′) , where X ′ = X [ 1.. n − 1 ] , and L is the largest integer such that the suffix X [ n − L + 1.. n ] is a substring of X ′. [ABSTRACT FROM AUTHOR]

In this work, we investigate the problem of maximizing nonmonotone DR-submodular function (possibly negative) subject to cardinality constraints on an integer lattice space. We propose a M -Threshold Decrease Algorithm that uses a compensation constant M from a special decomposition h (x) = f (x) − g (x) , which achieves a 1 − e − δ − ϵ approximation guarantee. To ensure that the algorithm ends in finite time, the supremum of δ is δ (ϵ) = ϵ max s ∈ Ω ⁡ h (χ s | 0) 2 k max s ∈ Ω ⁡ g (χ s | 0) + ϵ max s ∈ Ω ⁡ h (χ s | 0). If max s ∈ Ω ⁡ h (χ s | 0) > 2 k max s ∈ Ω ⁡ g (χ s | 0) , there exists ϵ ⁎ = arg ⁡ max ϵ ∈ (0 , 1) ⁡ 1 − e − δ (ϵ) − ϵ such that 1 − e − δ (ϵ ⁎) − ϵ ⁎ > 0. This implies that there is a valid δ such that 1 − e − δ − ϵ > 0. To accelerate the algorithm, we employ a random subset to replace the ground set and propose a Random M -Threshold Decrease Algorithm, where δ (ϵ) = ϵ r max s ∈ Ω ⁡ h (χ s | 0) 2 n k max s ∈ Ω ⁡ g (χ s | 0) + [ k (n − r) + ϵ r ] max s ∈ Ω ⁡ h (χ s | 0) with r being the size of the random subset and n being the size of the ground set. Furthermore, we demonstrate that, based on the DR-ratio γ d and the DS decomposition, the M -Threshold Decrease Algorithm is also suitable for solving the monotone non-DR-submodular maximization problem, achieving a 1 − e − γ d δ − O (ϵ) approximation guarantee. Because γ d is a challenging metric to calculate, we refine the M -Threshold Decrease Algorithm, which can return an estimate of γ d. To the best of our knowledge, this is the first time that a single factor approximation ratio has been proposed for the nonmonotone DR-submodular maximization problem (possibly negative) subject to cardinality constraints. • This paper adopts the decomposition structure to compensate the non-monotonicity and non-negativity for DR-submodular maximization. • Using a compensation constant M , we design a 1 − e − δ − ϵ approximation algorithm, namely M -Threshold Decrease Algorithm. • Based on the DR-ratio γ d , our algorithm is a 1 − e − δ γ d − O (ϵ) approximation algorithm for monotone non-DR-submodular maximization. [ABSTRACT FROM AUTHOR]

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in a shortest path between some pair of vertices of S. The Minimum Geodetic Set (MGS) problem is to find a geodetic set with minimum cardinality of a given graph. A grid embedding of a graph is a set of points in two dimensions with integer coordinates such that each point in the set represents a vertex of the graph and, for each edge, the points corresponding to its endpoints are at Euclidean distance 1. A graph is a partial grid if it has a grid embedding. In this paper, we first prove that Minimum Geodetic Set remains NP-hard even for subcubic partial grids of arbitrary girth. This jointly strengthens three existing hardness results: for bipartite graphs (Dourado et al. 2010 [11]), subcubic graphs (Bueno et al. 2018 [4]), and planar graphs (Chakraborty et al. 2020 [6]). The area of an internal face is the number of integer points lying on the boundary or interior of the face. A graph is a solid grid if it has a grid embedding such that all interior faces have area exactly four. To complement the above hardness result, we design a linear-time algorithm for Minimum Geodetic Set on solid grids, improving on a 3-approximation algorithm by Chakraborty et al. (2020) [6]. Our results hold for Edge Geodetic Set as well. A set S of vertices of a graph G is a geodetic set if every edge of G lies in a shortest path between some pair of vertices of S. The Minimum Edge Geodetic Set (MEGS) problem is to find an edge geodetic set with minimum cardinality of a given graph. As corollaries, we obtain that MEGS remains NP-hard on partial grids and is linear-time solvable on solid grids. [ABSTRACT FROM AUTHOR]

Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W (1 + τ) where τ is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Ω (W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct , the slack model enables a further asymptotic improvement. The main focus of the paper is on the widely studied Basic-Summing problem of computing the sum of the last W integers from { 0 , 1 ... , R } in a stream. While it is known that Ω (W log ⁡ R) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant τ. Specifically, for τ = Θ (1) , we present a space lower bound of Ω (log ⁡ (R W)) bits. Additionally, we show an Ω (log ⁡ (W / ϵ)) lower bound for RWϵ additive approximations and a Ω (log ⁡ (W / ϵ) + log ⁡ log ⁡ R) bits lower bound for (1 + ϵ) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [17] for (1 + ϵ) -multiplicative approximation that requires O (ϵ − 1 log ⁡ (R W) log ⁡ log ⁡ (R W)) space and performs updates in O (log ⁡ (R W)) worst case time. Finally, we show asymptotic improvements for the Count-Distinct , General-Summing , and Maximum problems. [ABSTRACT FROM AUTHOR]

In the field of parameterized counting complexity, the problems that are #W[1]-hard and admit fixed-parameter tractable randomized approximation scheme (FPTRAS) have attracted much attention in recent years. In this paper, we focus on the problems on parameterized counting matching and packing. These problems include counting set packing , counting matching , and counting subgraph packing (including both vertex-disjoint and edge-disjoint versions). We study the parameterized complexity on these problems. On the basis of some results for counting graph matchings, we show that a series of problems are #W[1]-hard. Furthermore, by extending the previous algorithm for counting 3- d matching , we obtain FPTRAS for each considered problem, respectively. Our results indicate that the problems on parameterized counting matching and packing form a large family of problems that are #W[1]-hard and admit FPTRAS. [ABSTRACT FROM AUTHOR]

An exact run in a string T is a non-empty substring of T that is a repetition of a smaller substring possibly followed by a prefix of it. Finding maximal exact runs in strings is an important problem and therefore a well-studied one in the area of stringology. For a given string T of length n , finding all maximal exact runs in the string can be done in O ( n log ⁡ n ) time on general ordered alphabets or O ( n ) time on integer alphabets. In this paper, we investigate the maximal approximate runs problem: for a given string T and a number k , find non-empty substrings T ′ of T such that changing at most k letters in T ′ transforms them into a maximal exact run. We present an O ( n k 2 log 2 ⁡ k + o c c ) algorithm to solve this problem, where occ is the number of substrings found. [ABSTRACT FROM AUTHOR]

For a collection F of graphs, the F - Contraction problem takes a graph G and an integer k as input and decides if G can be modified to some graph in F using at most k edge contractions. The F - Contraction problem is NP -Complete for several graph classes F. Heggernes et al. (2014) [4] initiated the study of F - Contraction in the realm of parameterized complexity. They showed that it is FPT if F is the set of all trees or the set of all paths. In this paper, we study F - Contraction where F is the set of all cactus graphs and show that we can solve it in 2 O (k) ⋅ | V (G) | O (1) time. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of partitioning a convex polygon P of n vertices into m polygons of equal area and perimeter. We give an algorithm for m = 2 that runs in O ( n ) time, and an algorithm for m = 2 k , where k is an integer, that runs in O ( ( 2 n ) k ) time. These are the first algorithms to solve this problem. [ABSTRACT FROM AUTHOR]