Search

We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper- and lower-bound tests against the counter value. Additionally, the counter updates associated with taking transitions can be (non-deterministically) scaled down by a nonzero factor between zero and one. Our three main results are as follows: we prove (1) that the reachability problem for COCA with global upper- and lower-bound tests is in NC 2 ; (2) that, in general, the problem is decidable in polynomial time; and (3) that it is NP-complete for COCA with parametric counter updates and bound tests.

Bipartite graphs widely exist in real-world scenarios and model binary relations like host-website, author-paper, and user-product. In bipartite graphs, a butterfly (i.e., $2\times 2$ bi-clique) is the smallest non-trivial cohesive structure and plays an important role in applications such as anomaly detection. Considerable efforts focus on counting butterflies in static bipartite graphs. However, they suffer from high time and space complexity when the bipartite graph of interest is given as a stream of edges. Although there are methods for approximately counting butterflies from bipartite graph streams, they suffer from either low accuracy or high time complexity. Therefore, it is still a challenge to accurately estimate butterfly counts from bipartite graph streams in a short time. To address this issue, we develop novel algorithms by exploiting the bipartite nature, which subtly integrates sampling and sketching techniques. We provide accurate estimators for butterfly counts and derive simple yet exact formulas for bounding their errors. We also conduct extensive experiments on a variety of real-world large bipartite graphs. Experimental results demonstrate that our algorithms are up to 20.0 times more accurate and up to 286.3 times faster than state-of-the-art methods under the same memory usage.

In this paper, we consider a probability maximizing shortest path problem. For a given directed graph with the length of each arc being an independent normal random variable with rational mean and standard deviation, the problem is to find a simple s − t path that maximizes the probability of arriving at the destination within a given limit. We first prove that the problem is NP -hard even on directed acyclic graphs with the mean of the length of each arc being restricted to an integer. Then, we present pseudo-polynomial time exact algorithms for the problem along with nontrivial special cases that can be solved in polynomial time. Finally, we present a fully polynomial approximation scheme (FPTAS) that iteratively solves deterministic shortest path problems. The structure of the proposed approximation scheme can be applied to devise FPTAS for other probability maximizing combinatorial optimization problems once the corresponding deterministic problems are polynomially solvable.

In the $\varepsilon$-Consensus-Halving problem, a fundamental problem in fair division, there are $n$ agents with valuations over the interval $[0,1]$, and the goal is to divide the interval into pieces and assign a label "$+$" or "$-$" to each piece, such that every agent values the total amount of "$+$" and the total amount of "$-$" almost equally. The problem was recently proven by Filos-Ratsikas and Goldberg [2019] to be the first "natural" complete problem for the computational class PPA, answering a decade-old open question. In this paper, we examine the extent to which the problem becomes easy to solve, if one restricts the class of valuation functions. To this end, we provide the following contributions. First, we obtain a strengthening of the PPA-hardness result of [Filos-Ratsikas and Goldberg, 2019], to the case when agents have piecewise uniform valuations with only two blocks. We obtain this result via a new reduction, which is in fact conceptually much simpler than the corresponding one in [Filos-Ratsikas and Goldberg, 2019]. Then, we consider the case of single-block (uniform) valuations and provide a parameterized polynomial time algorithm for solving $\varepsilon$-Consensus-Halving for any $\varepsilon$, as well as a polynomial-time algorithm for $\varepsilon=1/2$. Finally, an important application of our new techniques is the first hardness result for a generalization of Consensus-Halving, the Consensus-$1/k$-Division problem [Simmons and Su, 2003]. In particular, we prove that $\varepsilon$-Consensus-$1/3$-Division is PPAD-hard., Journal version. Preliminary version appeared at EC '20

The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal dominating sets of a graph $G=(V,E)$, one usually arrives at the problem to decide for a vertex set $U \subseteq V$, if there exists a \textit{minimal} dominating set $S$ with $U\subseteq S$. We propose a general, partial-order based formulation of such extension problems and study a number of specific problems which can be expressed in this framework. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimisation problem can be solved in polynomial time. This raises the question of how fixing a partial solution causes this increase in difficulty. In this regard, we study the parameterised complexity of extension problems with respect to parameters related to the partial solution, as well as the optimality of simple exact algorithms under the Exponential-Time Hypothesis. All complexity considerations are also carried out in very restricted scenarios, be it degree restrictions or topological restrictions (planarity) for graph problems or the size of the given partition for the considered extension variant of Bin Packing.

Weighted finite automata over the field of rational numbers and unary alphabets are considered. The notion of a characteristic polynomial is introduced for such automata as a means to provide a decidable necessary and sufficient condition, under which a unary weighted automaton admits a deterministic, i.e., sequential equivalent. The sequentiality problem for univariate rational series is thus proved to be decidable both over the rational numbers and over the integers, confirming a conjecture of S. Lombardy and J. Sakarovitch; its decidability over the nonnegative integers is observed as well. The decision algorithm proposed for these tasks is shown to run in polynomial time. A determinisation algorithm for determinisable unary weighted automata over the rational numbers is also described.

The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. Similarly, greedy algorithms deliver very good approximations to the optimal solution in practice. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that, on real instances, this leads to better approximations than the standard greedy approach within reasonable time., LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 25:1-25:14

For a fixed digraph G, the Constraint Satisfaction Problem with the template G, or CSP(G) for short, is the problem of deciding whether a given input digraph H admits a homomorphism to G. The dichotomy conjecture of Feder and Vardi states that CSP(G), for any choice of G, is solvable in polynomial time or NP-complete. This paper confirms the conjecture for a class of oriented trees called special triads. As a corollary we get the smallest known example of an oriented tree (with 33 vertices) defining an NP-complete CSP(G).

The K -sign depth ( K -depth) of a model parameter θ in a data set is the relative number of K -tuples among its residual vector that have alternating signs. The K -depth test based on K -depth, recently proposed by Leckey et al. (2020), is equivalent to the classical residual-based sign test for K = 2 , but is much more powerful for K ≥ 3 . This test has two major drawbacks. First, the computation of the K -depth is fairly time consuming having a polynomial time complexity of degree K , and second, the test requires knowledge about the quantiles of the test statistic which previously had to be obtained by simulation for each sample size individually. We tackle both of these drawbacks by presenting a limit theorem for the distribution of the test statistic and deriving an (asymptotically equivalent) form of the K -depth which can be computed efficiently. For K = 3 , such a limit theorem was already derived in Kustosz et al. (2016a) by mimicking the proof for U -statistics. We provide here a much shorter proof based on Donsker’s theorem and extend it to any K ≥ 3 . As part of the proof, we derive an asymptotically equivalent form of the K-depth which can be computed in linear time. This alternative and the original implementation of the K-depth are compared with respect to their runtimes and absolute difference.

Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, $K_t$-free unit $d$-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of $d$-contractions, witness that the twin-width is at most $d$. We show that FO model checking, that is deciding if a given first-order formula $\phi$ evaluates to true for a given binary structure $G$ on a domain $D$, is FPT in $|\phi|$ on classes of bounded twin-width, provided the witness is given. More precisely, being given a $d$-contraction sequence for $G$, our algorithm runs in time $f(d,|\phi|) \cdot |D|$ where $f$ is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarsk\'y et al. [FOCS '15]., Comment: 49 pages, 9 figures

Given an undirected graph G = ( V , E ) and a positive integer k ∈ 1 , … , | V | , we initiate the combinatorial study of stable sets of cardinality exactly k in G . Our aim is to instigate the polyhedral investigation of the convex hull of fixed cardinality stable sets, inspired by the rich theory on the classical structure of stable sets. We introduce a large class of valid inequalities to the natural integer programming formulation of the problem. We also present simple combinatorial relaxations based on computing maximum weighted matchings, which yield dual bounds towards finding minimum-weight fixed cardinality stable sets, and particular cases which are solvable in polynomial time.

Let G = ( V , E ) be an undirected graph, L G ∈ R V × V be the associated Laplacian matrix, and b ∈ R V be a vector. Solving the Laplacian system L G x = b has numerous applications in theoretical computer science, machine learning, and network analysis. Recently, the notion of the Laplacian operator L F : R V → 2 R V for a submodular transformation F : 2 V → R + E was introduced, which can handle undirected graphs, directed graphs, hypergraphs, and joint distributions in a unified manner. In this study, we show that the submodular Laplacian system L F ( x ) ∋ b can be solved in polynomial time. Furthermore, we prove that even when the submodular Laplacian system has no solution, we can solve its regression form in polynomial time. Finally, we discuss potential applications of submodular Laplacian systems in machine learning and network analysis.

We consider the classic Facility Location, k -Median, and k -Means problems in metric spaces of doubling dimension d . We give nearly linear-time approximation schemes for each problem. The complexity of our algorithms is Õ(2 (1/ε) O(d2) n) , making a significant improvement over the state-of-the-art algorithms that run in time n (d/ε) O(d) . Moreover, we show how to extend the techniques used to get the first efficient approximation schemes for the problems of prize-collecting k -Median and k -Means and efficient bicriteria approximation schemes for k -Median with outliers, k -Means with outliers and k -Center.

Symport/antiport P systems with membrane division are parallel computing models, which can solve NP-complete problems in polynomial time. In this paper, promoters are incorporated into symport/antiport P systems with membrane division, and a new kind of P systems, called symport/antiport P systems with promoters and membrane division (SAPD P systems, for short) is proposed. The computational efficiency of SAPD P systems is investigated. We show that a uniform solution to the QSAT problem is given by using only symport rules of length at most 2 and promoters of length at most 1 in a polynomial time (Note that the QSAT problem can be solved by symport/antiport P systems with membrane division using both symport rules and antiport rules of length at most 3 (Song et al. in BioSystems 130: 51–58, 2015)).

In the literature on multi-scenario scheduling problems, it is assumed that (i) each scenario defines a different possible realization of the job’s parameters; and (ii) the value of each parameter is arbitrary for any job in any scenario. Under these assumptions many multi-scenario scheduling problems have been proven to be $$\mathcal {NP}$$ -hard. We study a special case of this set of problems, in which there is an agreeable condition between scenarios on the processing-time parameters. Accordingly, the processing time of job $$J_{j}$$ under scenario $$s_{i}$$ is at most its value under scenario $$s_{i+1}$$ , for $$i=1,\ldots q-1$$ , where q is the number of different possible scenarios. We focus on three classical scheduling problems for which the single-scenario case is solvable in polynomial time, while the multi-scenario case is $$\mathcal {NP}$$ -hard, even when there are only two scenarios. The three scheduling problems consist of minimizing either the total completion time or the number of tardy jobs on a single machine, and minimizing the makespan in a two-machine flow-shop system. We show that the multi-scenario version of all three problems remains $$\mathcal {NP}$$ -hard even when processing times are agreeable and there are only two scenarios. We also show that for a more specific structure of job processing times two out of the three problems become easy to solve, while the complexity status of the third remains open for future research.

Network interdiction problems by upgading critical edges/nodes have important applications to reduce the infectivity of the COVID-19. A network of confirmed cases can be described as a rooted tree that has a weight of infectious intensity for each edge. Upgrading edges (nodes) can reduce the infectious intensity with contacts by taking prevention measures such as disinfection (treating the confirmed cases, isolating their close contacts or vaccinating the uninfected people). We take the sum of root-leaf distance on a rooted tree as the whole infectious intensity of the tree. Hence, we consider the sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees (SDIPT-UE/N). The problem (SDIPT-UE) aims to minimize the sum of root-leaf distance by reducing the weights of some critical edges such that the upgrade cost under some measurement is upper-bounded by a given value. Different from the problem (SDIPT-UE), the problem (SDIPT-UN) aims to upgrade a set of critical nodes to reduce the weights of the edges adjacent to the nodes. The relevant minimum cost problem (MCSDIPT-UE/N) aims to minimize the upgrade cost on the premise that the sum of root-leaf distance is upper-bounded by a given value. We develop different norms to measure the upgrade cost. Under weighted Hamming distance, we show the problems (SDIPT-UE/N) and (MCSDIPT-UE/N) are NP-hard by showing the equivalence of the two problems and the 0–1 knapsack problem. Under weighted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$l_1$$\end{document}l1 norm, we solve the problems (SDIPT-UE) and (MCSDIPT-UE) in O(n) time by transforimg them into continuous knapsack problems. We propose two linear time greedy algorithms to solve the problem (SDIPT-UE) under unit Hamming distance and the problem (SDIPT-UN) with unit cost, respectively. Furthermore, for the the minimum cost problem (MCSDIPT-UE) under unit Hamming distance and the problem (MCSDIPT-UN) with unit cost, we provide two \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document}O(nlogn) time algorithms by the binary search methods. Finally, we perform some numerical experiments to compare the results obtained by these algorithms.

It is known that polarizationless P systems with active membranes can solve $$\mathrm {PSPACE}$$ PSPACE -complete problems in polynomial time without using in-communication rules but using the classical (also called strong) non-elementary membrane division rules. In this paper, we show that this holds also when in-communication rules are allowed but strong non-elementary division rules are replaced with weak non-elementary division rules, a type of rule which is an extension of elementary membrane divisions to non-elementary membranes. Since it is known that without in-communication rules, these P systems can solve in polynomial time only problems in $$\mathrm {P}^{\text {NP}}$$ P NP , our result proves that these rules serve as a borderline between $$\mathrm {P}^{\text {NP}}$$ P NP and $$\mathrm {PSPACE}$$ PSPACE concerning the computational power of these P systems.

In this paper, we discuss the copy complexity of Horn formulas with respect to unit resolution. A Horn formula is a boolean formula in conjunctive normal form (CNF) with at most one positive literal per clause. Horn formulas find applications in a number of domains, such as program verification (abstract interpretation) and logic programming (answer set programming). Quantified Horn clauses are used extensively in temporal verification of universal properties. Resolution is one of the oldest proof systems (refutation systems) for the boolean satisfiability problem (SAT), when the input is presented in conjunctive normal form (CNF). It is both sound and complete, although inefficient, when compared to other stronger proof systems for boolean formulas. Despite its inefficiency, the simple nature of resolution makes it an integral part of several theorem provers. Unit resolution is a restricted form of resolution in which each resolution step needs to use a clause with only one literal (unit literal clause). While not complete for general CNF formulas, unit resolution is complete for Horn formulas. Read-once resolution is a form of resolution in which each clause (input or derived) may be used in at most one resolution step. As with unit resolution, read-once resolution is incomplete in general and complete for Horn clauses. This paper focuses on a combination of unit resolution and read-once resolution called unit read-once resolution. Unit read-once resolution is incomplete for Horn clauses. In this paper, we study the copy complexity problem in Horn formulas with respect to unit read-once resolution. Briefly, the copy complexity of a formula with respect to unit read-once resolution, is the smallest number k, such that replicating each clause k times guarantees the existence of a unit read-once resolution refutation (UROR). This paper focuses on two problems related to the copy complexity of Horn formulas with respect to unit read-once resolution. We first relate the copy complexity of Horn formulas with respect to unit read-once resolution to the copy complexity of the corresponding Horn constraint system with respect to the addition rule. We also examine a form of copy complexity in which we permit replication of derived clauses, in addition to the input clauses. Finally, we provide a polynomial time algorithm for the problem of checking if a 2-CNF formula has a UROR.

In the constrained synchronization problem we want to know if a given input automaton admits a synchronizing word contained in a (fixed) regular constraint language. Here we study the computational complexity of the constrained synchronization problem for the class of regular commutative constraint languages and the computational complexity of the problem restricted to commutative input semi-automata. We give a full classification of the computational complexity of the constrained synchronization problem for commutative regular constraints. Depending on the constraint language, our problem becomes PSPACE -complete, NP -complete or polynomial time solvable. In addition, we derive a polynomial time decision procedure for the complexity of the constrained synchronization problem, given a constraint automaton accepting a commutative language as input. Furthermore, for commutative input semi-automata, the problem is decidable in polynomial time, regardless of the regular constraint language.

The urgency of the problem of memory testing of modern computing systems is shown. Mathematical models describing the faulty states of storage devices and the methods used for their detection are investigated. The concept of address sequences (pA) with an even repetition of addresses is introduced, which are the basis of the basic element included in the structure of the new transparent march tests March _pA_1 and March _pA_2. Algorithms for the formation of such sequences and examples of their implementations are given. The maximum diagnostic ability of new tests is shown for the case of the simplest faults, such as constant (SAF) and transition faults (TF), as well as for complex pattern sensitive faults (PNPSFk). There is a significantly lower time complexity of the March_pA_1 and March_pA_2 tests compared to classical transparent tests, which is achieved at the expense of less time spent on obtaining a reference signature. New distance metrics are introduced to quantitatively compare the effectiveness of the applied pA address sequences in a single implementation of the March_pA_1 and March_pA_2 tests. The basis of new metrics is the distance D(A(j), pA) determined by the difference between the indices of repeated addresses A(j) in the sequence pA. The properties of new characteristics of the pA sequences are investigated and their applicability is evaluated for choosing the optimal test pA sequences that ensure the high efficiency of new transparent tests. Examples of calculating distance metrics are given and the dependence of the effectiveness of new tests on the numerical values of the distance metrics is shown. As well as in the case of classical transparent tests, multiple applications of new March_pA_1 and March_pA_2 tests are considered. The characteristic V(pA) is introduced, which is numerically equal to the number of different values of the distance D(A(j), pA) of addresses A(j) of the sequence pA. The validity of analytical estimates is experimentally shown and high efficiency of fault detection by the tests March_pA_1 and March_pA_2 is confirmed by the example of coupling faults for p = 2.

A standard way of justifying that a certain probabilistic property holds in a system is to provide a witnessing subsystem (also called critical subsystem) for the property. Computing minimal witnessing subsystems is NP-hard already for acyclic Markov chains, but can be done in polynomial time for Markov chains whose underlying graph is a tree. This paper considers the problem for probabilistic systems that are similar to trees or paths. It introduces the parameters directed tree-partition width (dtpw) and directed path-partition width (dppw) and shows that computing minimal witnesses remains NP-hard for Markov chains with bounded dppw (and hence also for Markov chains with bounded dtpw). By observing that graphs of bounded dtpw have bounded width with respect to all known tree similarity measures for directed graphs, the hardness result carries over to these other tree similarity measures. Technically, the reduction proceeds via the conceptually simpler matrix-pair chain problem, which is introduced and shown to be NP-complete for nonnegative matrices of fixed dimension. Furthermore, an algorithm which aims to utilise a given directed tree partition of the system to compute a minimal witnessing subsystem is described. It enumerates partial subsystems for the blocks of the partition along the tree order, and keeps only necessary ones. A preliminary experimental analysis shows that it outperforms other approaches on certain benchmarks which have directed tree partitions of small width., In Proceedings GandALF 2021, arXiv:2109.07798. A full version of this paper, containing all proofs, appears at arXiv:2108.08070

We provide a graphical treatment of SAT and #SAT on equal footing. Instances of #SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over C in terms of diagrams built from simple generators, in which computation may be carried out by transformations of diagrams alone. In general, nodes of ZH diagrams take parameters over C which determine the tensor coefficients; for the standard representation of #SAT instances, the coefficients take the value 0 or 1. Then, by choosing the coefficients of a diagram to range over B, we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the decision or counting version of the problem. We find that for classes known to be in P, such as 2SAT and #XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as 3SAT, or #P-complete, such as #2SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and #CSPs and shows promise in aiding tensor network contraction-based algorithms., Comment: In Proceedings QPL 2020, arXiv:2109.01534

We present a framework for constructing congruence closure modulo permutation equations, which extends the abstract congruence closure framework for handling permutation function symbols. Our framework also handles certain interpreted function symbols satisfying each of the following properties: idempotency (I), nilpotency (N), unit (U), I U U, or N U U. Moreover, it yields convergent rewrite systems corresponding to ground equations containing permutation function symbols. We show that congruence closure modulo a given finite set of permutation equations can be constructed in polynomial time using equational inference rules, allowing us to provide a polynomial time decision procedure for the word problem for a finite set of ground equations with a fixed set of permutation function symbols., Comment: In Proceedings SCSS 2021, arXiv:2109.02501

In this paper, we study the problem of finding read-once refutations (ROR) of linear feasibility in a specialized class of constraint systems called UTVPI+ constraint systems ( UCS + ). The refutations in this paper are analyzed using the ADD inference rule. Recall that a Unit Two Variable Per Inequality (UTVPI) constraint is a constraint of the form a i ⋅ x i + a j ⋅ x j ≤ b , where b ∈ Z , and a i , a j ∈ { 0 , 1 , − 1 } . A conjunction of such constraints is called a UTVPI constraint system (UCS). UCSs find applications in a number of domains such as abstract interpretation and scheduling. We examine a more general form of UCSs that allows for a limited number of non-UTVPI constraints to be added to a UCS. We refer to these more general UCSs as UTVPI+ constraint systems or UCS + s . If a UCS + has only k non-UTVPI constraints, then we refer to it as a UCS k + . Our focus in this paper is on refutations, i.e., proofs of infeasibility in UCS + s . In particular, we study read-once refutations of linear feasibility in UCS + s . Although the problem of finding read-once refutations of UCSs is polynomial time solvable, the presence of non-UTVPI constraints makes the problem NP-hard. However, if the number of non-UTVPI constraints is fixed, then read-once refutations can be found in polynomial time. In fact, in this paper, we show that the ROR problem is fixed-parameter tractable (FPT) for UCS k + s , with respect to k, the number of non-UTVPI constraints in the system. We also provide a lower bound on the efficiency of a class of parameterized algorithms for this problem, based on the Strong Exponential Time Hypothesis.

The problem of computing the meet over all paths (MOP) solution in a monotone data flow framework over an infinite meet semilattice is generally undecidable [1] . Hence, the maximum fixed point (MFP) solution, which is polynomial time computable on semi-lattices of finite height, is generally used in practice for program analysis questions in monotone data flow frameworks. However, we show that if the semi-lattice is finite, computing MOP solution is NL -complete with respect to log space reductions, which implies parallelizability and polynomial time computability. It is also shown that the problem of computing the maximum fixed point (MFP) solution is P -complete with respect to log space reductions, and hence not efficiently parallelizable, even when the flow graph is directed acyclic and the semilattice has just four elements. These results appear in contrast with the fact that when the semilattice is not finite, solving the MOP problem is significantly harder than MFP.

This work addresses the balanced connected k -partition problem ( BCP k ), which is formally defined as follows. Given a connected graph G = ( V , E ) with nonnegative weights on the vertices, find a partition { V i } i = 1 k of V such that each class V i induces a connected subgraph of G , and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP -hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCP k is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose three linear programming formulations for BCP k . The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. The other two formulations are based on flows and have a polynomial number of constraints and variables. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other exact approaches presented in the literature.

Unlike qualitative properties such as correctness (safety and liveness), quantitative properties of distributed algorithms have only been certified in very few works. This work is the first attempt to certify time complexity bounds of fault-tolerant distributed algorithms. Our case study consists in formally proving, using the Coq proof assistant, the time complexity of the first Dijkstra’s self-stabilizing token ring algorithm. In more detail, we formally prove both the self-stabilization and exact worst-case stabilization time of this algorithm assuming fully asynchronous settings. This latter result is obtained in two main steps. First, we certify a non-trivial upper bound on the stabilization time, i.e., every execution contains at most steps, where N is the number of nodes. Then, we exhibit, for every ring of at least four nodes, a possible execution whose complexity exactly matches that upper bound. Notice that this tight bound was unknown until now, even among self-stabilization researchers.

Many geometric optimization problems can be reduced to finding points in space (centers) minimizing an objective function which continuously depends on the distances from the centers to given input points. Examples are k-Means, Geometric k-Median/Center, Continuous Facility Location, m-Variance, etc. We prove that, for any fixed $$\varepsilon >0$$ , every set of n input points in fixed-dimensional space with the metric induced by any vector norm admits a set of O(n) candidate centers which can be computed in almost linear time and which contains a $$(1+\varepsilon )$$ -approximation of each point of space with respect to the distances to all the input points. It gives a universal approximation-preserving reduction of geometric center-based problems with arbitrary continuity-type objective functions to their discrete versions where the centers are selected from a fairly small set of candidates. The existence of such a linear-size set of candidates is also shown for any metric space of fixed doubling dimension.

The Rao-Nam cryptosystem is a symmetric version of the McEliece code-based cryptosystem proposed to get rid of the shortcomings inherent in the first symmetric code-based encryption schemes. Almost immediately after the publication of this cryptosystem, attacks on it based on selected plaintexts appeared, which led to the emergence of various improvements and modifications of the original cryptosystem. The secret key in the traditional Rao-Nam scheme is a certain Boolean matrix and a set of binary vectors used to generate distortions during encryption. Such vectors must have different syndromes, that is, be different modulo of the code generated by the rows of the specified matrix. The original work of Rao and Nam considered two methods of forming the set of these vectors, the first of which consists in using predetermined vectors of sufficiently large weight, and the second is random selection of these vectors according to the equiprobable scheme. It is known that the first option does not provide the proper security of the Rao – Nam cryptosystem (due to the small number and simple structure of these vectors), but the second option is more meaningful and requires additional research. The purpose of this paper is to obtain estimates of the effectiveness (time complexity for a given upper bound of the error probability) of attacks on a cryptosystem, which generalizes the traditional Rao – Nam scheme to the case of a finite Abelian group (note that the need to study such versions of the Rao – Nam cryptosystem is due to their consideration in recent publications). Two attacks, based on selected plaintext, are presented. The first of them is not mentioned in the works known to the authors of this article and, under certain well-defined conditions, it allows recovering the secret key of the cryptosystem with quadratic complexity. The second attack is a generalized and simplified version of the well-known Struik-van Tilburg attack. It is shown that the complexity of this attack depends on the power of the stabilizer of the set of vectors, which forms the second part of the key, in the translation group of the Abelian group, over which the Rao – Nam cryptosystem is considered. In this paper, a bound is obtained for the probability of triviality of the stabilizer under the condition of random choice of this set. From the obtained bound, it follows that Struik-van Tilburg attack is, on average, noticeably more efficient than the worst case considered earlier.

The capacitated vehicle routing problem (CVRP) is a classical combinatorial optimization problem having a wide range of practically important applications in operations research. As most combinatorial problems, CVRP is strongly NP-hard (even on the Euclidean plane). A metric instance of CVRP is APX-complete, so it cannot be approximated to arbitrary prescribed accuracy in the class of polynomial time algorithms (assuming that $$P \ne NP$$ ). Nevertheless, in the case of finite-dimensional Euclidean spaces, a quasi-polynomial or even polynomial time approximation scheme can be found for the problem by applying an approach based on works by S. Arora, A. Das, and C. Mathieu. Below, this approach has been extended for the first time to a significantly larger class of metric spaces of fixed doubling dimension. It is shown that CVRP formulated in such a space has a quasi-polynomial time approximation scheme whenever the number of routes in its optimal solution is bounded above by a polynomial in the logarithm of the input size.

We consider a multiple-depots extension of the classic Hamiltonian path problem where k salesmen are initially located at different depots. To the best of our knowledge, no algorithm for this problem with a constant approximation ratio has been previously proposed, except for some special cases. We present a polynomial algorithm with a tight approximation ratio of $$\max \left\{ \frac{3}{2},2-\frac{1}{k}\right\} $$ for arbitrary $$k\geqslant 1$$ , and an algorithm with approximation ratio $$\frac{5}{3}$$ that runs in polynomial time for fixed k. Moreover, we develop a recursive framework to improve the approximation ratio to $$\frac{3}{2}+\epsilon $$ . This framework is polynomial for fixed k and $$\epsilon $$ , and may be useful in improving the Christofides-like heuristics for other related multiple salesmen routing problems.

We study the reachability problem for queue automata and lossy queue automata. Concretely, we consider the set of queue contents which are forwards resp. backwards reachable from a given set of queue contents. Here, we prove the preservation of regularity if the queue automaton loops through some special sets of transformation sequences. This is a generalization of the results by Boigelot et al. and Abdulla et al. regarding queue automata looping through a single sequence of transformations. We also prove that our construction is possible in polynomial time.

Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ, referred to as Δ-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the feedback vertex number or the pathwidth of the underlying graph. The main question thus is whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work., LIPIcs, Vol. 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020), pages 30:1-30:18

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions.The input consists of a set of jobs, characterized by their processing times, release times, and weights and we want to compute a (possibly preemptive) schedule for them. The objective is to minimize the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its release date and its completion time.It had been a long-standing open problem to find a polynomial time O(1)-approximation algorithm for this setting. In a recent break-through result, Batra, Garg, and Kumar (FOCS 2018) found such an algorithm if the input data are polynomially bounded integers, and Feige, Kulkarni, and Li (SODA 2019) presented a black-box reduction to this setting. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10000. In this paper we improve this ratio to 2+ε. The algorithm by Batra, Garg, and Kumar (FOCS 2018) reduces the problem to Demand MultiCut on trees and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor 1+ε, and then solve its resulting instances up to a factor of 2+ε by a dynamic program. In particular, our reduction ensures certain structural properties, thanks to which we do not need LP-rounding methods.We believe that our result makes substantial progress towards finding a PTAS for weighted flow time on a single machine.

In this paper, an original reduction algorithm for solving simultaneous multivariate polynomial equations is presented. The algorithm is exponential in complexity, but the well-known algorithms, such as the extended Euclidean algorithm and Buchberger's algorithm, are superexponential. The superexponential complexity of the well-known algorithms is due to their not being "minimal" in a certain sense. Buchberger's algorithm produces a Groebner basis. The proposed original reduction algorithm achieves the required task, via computation of determinants of parametric Sylvester matrices, and produces a Rabin basis, which is shown to be minimal, when two multivariate polynomials are reduced at a time. The minimality of Rabin basis allows us to prove exponential lower bounds for the space complexity of an algebraic proof of certification, for a specific computational problem in the computational complexity class PSPACE, showing that the complexity classes PSPACE and P cannot be the same. By the same reasoning, it follows that Co-NP is not the same as either of the complexity classes NP and P, and that the polynomial time hierarchy does not collapse. It is also shown that the class BPP of languages decidable by bounded error probabilistic algorithms with (probabilistic) polynomial time proofs for the membership of input words is not the same as any one of the complexity classes P, NP and Co-NP. It follows again, from the discussions, that the complexity classes NP and P are not the same, by relativization of BPP, with respect to P and NP.

We consider the problem of computing the triplet distance between two rooted unordered trees with n labeled leaves. Introduced by Dobson in 1975, the triplet distance is the number of leaf triples that induce different topologies in the two trees. The current theoretically fastest algorithm is an O( n log n ) algorithm by Brodal et al. (SODA 2013). Recently, Jansson and Rajaby proposed a new algorithm that, while slower in theory, requiring O( n log 3 n ) time, in practice it outperforms the theoretically faster O( n log n ) algorithm. Both algorithms do not scale to external memory. We present two cache oblivious algorithms that combine the best of both worlds. The first algorithm is for the case when the two input trees are binary trees, and the second is a generalized algorithm for two input trees of arbitrary degree. Analyzed in the RAM model, both algorithms require O( n log n ) time, and in the cache oblivious model O( n / B log 2 n / M ) I/Os. Their relative simplicity and the fact that they scale to external memory makes them achieve the best practical performance. We note that these are the first algorithms that scale to external memory, both in theory and in practice, for this problem.

We study the problem of counting the repairs of an inconsistent database in the case where constraints are Functional Dependencies (FDs). A repair is then a maximal independent set of the conflict graph, wherein nodes represent facts and edges represent violations. We establish a dichotomy in data complexity for the complete space of FDs: when the FD set has, up to equivalence, what we call a “left-hand-side chain,” the repairs can be counted in polynomial time; otherwise, the problem is ♯ P -complete. Moreover, the property of having a left-hand-side chain up to equivalence coincides with the condition that the conflict graph of every inconsistent database for the schema is P 4 -free, and it is polynomial-time decidable.

We consider a Two-Bar Charts Packing Problem (2-BCPP), in which it is necessary to pack two-bar charts (2-BCs) in a unit-height strip of minimum length. The problem is a generalization of the Bin Packing Problem. Earlier, we proposed an $$O(n^2)$$ –time algorithm that constructs the packing of n arbitrary 2-BCs, whose length is at most $$2\cdot OPT+1$$ , where OPT is the minimum packing length. This paper proposes two new 3/2–approximate algorithms based on sequential matching. One has time complexity $$O(n^4)$$ and is applicable when at least one bar of each 2-BC is greater than 1/2. Another has time complexity $$O(n^{3.5})$$ and is applicable when, additionally, all BCs are non-increasing or non-decreasing. We prove the estimate’s tightness and conduct a simulation to compare the constructed packings with the optimal solutions or a lower bound of optimum.

In a cardinality constrained inverse center location problem on networks, the goal is to modify the edge lengths at the minimum total cost subject to the given modification bounds so that a prespecified vertex becomes an absolute center location of the underlying network under the perturbed edge lengths and further the cardinality of the modified edge lengths obeys an upper bound. Using a set of self-constructed red-black search trees, as a suitable data structure, we propose novel optimal algorithms with polynomial time complexities for the problem on tree networks under various cost norms.

In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in $\mathcal{O}(n^2)$ time., Comment: 30 pages, 10 figures; accepted at STACS 2020

Functional encryption (FE) is a novel cryptographic paradigm. In comparison to conventional encryption schemes, FE allows producing secret keys $$sk_f$$ corresponding to a function f that decrypt encryptions of $$x_0$$ to $$f(x_0)$$ . Recently, Lin proposed FE for arbitrary degree polynomials from the SXDH assumption to an exact multilinear map (CRYPTO’17). However, there is no concrete instantiation of the scheme in the absence of an exact multilinear map. Although Lin’s FE can be instantiated by noisy multilinear maps such as the GGH13, CLT13, and GGH15 schemes, the security of FE instantiated by noisy multilinear maps is unclear. In this paper, we point out the weakness of the Lin’s FE when it is instantiated by well-known candidates of noisy multilinear maps. In other words, we present a polynomial time attack of the FE on each noisy multilinear map. In the proposed method, our attack captures Lin’s FE for arbitrary degree polynomials instantiated by GGH13 and CLT13 and is also applicable to FE for polynomials of degree $$O(\log _2 \lambda )$$ when instantiated by GGH15 under the current parameters where $$\lambda $$ is the security parameter.

The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of probability measures with finite support. In this paper, we show that finding a barycenter of sparse support is hard, even in dimension 2 and for only 3 measures. We prove this claim by showing that a special case of an intimately related decision problem SCMP—does there exist a measure with a non-mass-splitting transport cost and support size below prescribed bounds? Is NP-hard for all rational data. Our proof is based on a reduction from planar 3-dimensional matching and follows a strategy laid out by Spieksma and Woeginger (Eur J Oper Res 91:611–618, 1996) for a reduction to planar, minimum circumference 3-dimensional matching. While we closely mirror the actual steps of their proof, the arguments themselves differ fundamentally due to the complex nature of the discrete barycenter problem. Containment of SCMP in NP will remain open. We prove that, for a given measure, sparsity and cost of an optimal transport to a set of measures can be verified in polynomial time in the size of a bit encoding of the measure. However, the encoding size of a barycenter may be exponential in the encoding size of the underlying measures.

We investigate the computational complexity of the graph primality testing problem with respect to the direct product (also known as Kronecker, cardinal or tensor product). In [1] Imrich proves that both primality testing and a unique prime factorization can be determined in polynomial time for (finite) connected and nonbipartite graphs. The author states as an open problem how results on the direct product of nonbipartite, connected graphs extend to bipartite connected graphs and to disconnected ones. In this paper we partially answer this question by proving that the graph isomorphism problem is polynomial-time many-one reducible to the graph compositeness testing problem (the complement of the graph primality testing problem). As a consequence of this result, we prove that the graph isomorphism problem is polynomial-time Turing reducible to the primality testing problem. Our results show that connectedness plays a crucial role in determining the computational complexity of the graph primality testing problem.

Broadcast consensus protocols (BCPs) are a model of computation, in which anonymous, identical, finite-state agents compute by sending/receiving global broadcasts. BCPs are known to compute all number predicates in $\mathsf{NL}=\mathsf{NSPACE}(\log n)$ where $n$ is the number of agents. They can be considered an extension of the well-established model of population protocols. This paper investigates execution time characteristics of BCPs. We show that every predicate computable by population protocols is computable by a BCP with expected $\mathcal{O}(n \log n)$ interactions, which is asymptotically optimal. We further show that every log-space, randomized Turing machine can be simulated by a BCP with $\mathcal{O}(n \log n \cdot T)$ interactions in expectation, where $T$ is the expected runtime of the Turing machine. This allows us to characterise polynomial-time BCPs as computing exactly the number predicates in $\mathsf{ZPL}$, i.e. predicates decidable by log-space bounded randomised Turing machine with zero-error in expected polynomial time where the input is encoded as unary., Comment: To be published in the Proceedings of the 24th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), 2021

In the present paper, we propose the efficient algorithm for the parameter reduction of soft sets and we implement it in diagnosing the risk of heart disease problem. Moreover, the efficiency of the algorithm is investigated. The time complexity of the $${\textit{Map}}_-{\textit{Matix}}$$ is given by total number of comparisons made to construct $${\textit{map}}_-{\textit{matrix}}$$ . For n number of objects and f number of attributes, the total number of comparisons is $$n \times f$$ . Therefore, the time complexity is given O(nf). The algorithm $${\textit{Generate}}_-{\textit{Powerset}}$$ takes the total of features f as input and its time complexity is given by $$O(2^f)$$ . Moreover, the overall efficiency is given by $$O(2^f)$$ .

Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of length N. Our algorithm has a time complexity of $$\tilde{O}(\sqrt{N})$$ O ̃ ( N ) , while the space complexity remains modest at O(N + M). We report the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes.

We consider the sparse phase retrieval problem of recovering a sparse signal $\mathbf {x}$ in $\mathbb {R}^d$ from intensity-only measurements in dimension $d \geq 2$ . Sparse phase retrieval can often be equivalently formulated as the problem of recovering a signal from its autocorrelation, which is in turn directly related to the combinatorial problem of recovering a set from its pairwise differences. In one spatial dimension, this problem is well studied and known as the turnpike problem . In this work, we present MISTR (Multidimensional Intersection Sparse supporT Recovery), an algorithm which exploits this formulation to recover the support of a multidimensional signal from magnitude-only measurements. MISTR takes advantage of the structure of multiple dimensions to provably achieve the same accuracy as the best one-dimensional algorithms in dramatically less time. We prove theoretically that MISTR correctly recovers the support of signals distributed as a Gaussian point process with high probability as long as sparsity is at most $\mathcal {O}(n^{d\theta })$ for any $\theta , where $n^d$ represents pixel size in a fixed image window. In the case that magnitude measurements are corrupted by noise, we provide a thresholding scheme with theoretical guarantees for sparsity at most $\mathcal {O}(n^{d\theta })$ for $\theta that obviates the need for MISTR to explicitly handle noisy autocorrelation data. Detailed and reproducible numerical experiments demonstrate the effectiveness of our algorithm, showing that in practice MISTR enjoys time complexity which is nearly linear in the size of the input.

Given a piecewise-defined function, checking whether it is convex is a nontrivial task. While it may be easy to check whether the restriction of the function to each piece is convex, ensuring the e...

The Shell sort algorithm is one of the most practically effective in-place sorting algorithms. However, it is difficult to execute this algorithm with its intended running time complexity on data encrypted using fully homomorphic encryption (FHE), because the insertion sort in Shell sort has to be performed by considering the worst-case input data. In this paper, in order for the sorting algorithm to be used on the FHE data, we modify the Shell sort with an additional parameter $\alpha $ , allowing exponentially small sorting failure probability. For a gap sequence of powers of two, the modified Shell sort with input array length $n$ is found to have the trade-off between the running time complexity of $O(n^{3/2}\sqrt {\alpha +\log \log n})$ and the sorting failure probability of $2^{-\alpha }$ . Its running time complexity is close to the intended running time complexity of $O(n^{3/2})$ and the sorting failure probability can be made very low with slightly increased running time. Further, the near-optimal window length of the modified Shell sort is also derived via convex optimization. The proposed analysis of the modified Shell sort is numerically confirmed by using randomly generated arrays. For the practical aspect, our modification can be applied to any gap sequence, and we show that Ciura’s gap sequence, which is known to have good practical performance, is also practically effective when our modified Shell sort is applied. We compare our modified Shell sort with other sorting algorithms with the FHE over the torus (TFHE) library, and it is shown that this modified Shell sort has the best performance in running time among in-place sorting algorithms on homomorphic encryption scheme.