Search

Ker-I Ko (葛可一, 1950-2018) made multiple pioneering and milestone contributions to structural complexity theory and real-number computation. His sharp perception of both discrete and continuous structures had led him to study fundamental concepts from one-way functions [29] , to polynomial-time hierarchy [21] , from integral equations [24] , to real functions [28] , from fractals [27] to fixed-points [25] , from optimization [20] to relativization [22] , from instance complexity [36] to real complexity [28] , from NP-completeness [31] to exponential-time completeness [23]. In his final two years, he turned his focus to game-theoretical designs for dynamic processes over social networks [12,33]. For this honorary special issue in memory of Professor Ker-I Ko , we are pleased to be able to contribute a paper with scope intersecting the areas that drew his last attention, and with results connecting discrete and continuous formulations of network dynamics. We prove that the complex stochastic network-influence processes have a simple graph-theoretical basis: Every stochastic-cascading influence profile can be written as a linear combination of breadth-first-search-based broadcast-propagations over layered-graphs. This graph-theoretical basis of stochastic network influence provides us with a systematic framework for studying the following fundamental question in network analysis: How should one assess the centralities of nodes in an information/influence propagation process over a social network? Our framework systematically extends a family of classical graph-theoretical centrality formulations — including degree centrality, harmonic centrality, and various notions of "sphere-of-influence" — to influence-based network centralities. Given that group cooperation is essential in social influences, we further extend natural group centralities from graph models to influence models, enabling us to assess individuals' centralities in group influence settings by applying the fundamental concept of Shapley value from cooperative game theory. Mathematically, using the property that these centrality formulations are Bayesian, 3 we prove an axiomatic characterization theorem: Every influence-based centrality formulation in this family is the unique Bayesian centrality that conforms with its corresponding graph-theoretical centrality. Moreover, the uniqueness is fully determined by the centrality formulation on the class of layered graphs, which is derived from a beautiful algebraic structure of influence instances modeled by cascading sequences. We further provide an algorithmic framework for efficient approximation of these influence-based centrality measures. Our study provides us with a systematic road map for comparative analyses of different influence-based centrality formulations. The fact that layered graphs form a basis for the space of influence-cascading-sequence profiles could also be useful in other studies of network influences. [ABSTRACT FROM AUTHOR]

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, addition, and multiplication is allowed turns out to be equivalent to the complement of polynomial identity testing (PIT). Our results imply the following improvements and insights on problems studied in earlier papers. We improve the bounds for the membership problem MC (∪ , ∩ , x ‾ , + , ×) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ (∪ , ∩ , x ‾ , + , ×) studied by Glaßer et al. 2010. Moreover, it turns out that the following problems are equivalent to PIT, which shows that the challenge to improve their bounds is just a reformulation of a well-studied, major open problem in algebraic computing complexity: • membership problem MC (∩ , + , ×) studied by McKenzie and Wagner 2007 • integer membership problems MC Z (+ , ×) , MC Z (∩ , + , ×) studied by Travers 2006 • equivalence problem EQ (+ , ×) studied by Glaßer et al. 2010. [ABSTRACT FROM AUTHOR]

Kingdomino TM is a board game designed by Bruno Cathala and edited by Blue Orange since 2016. The goal is to place 2 × 1 dominoes on a grid layout, and get a better score than other players. Each 1 × 1 domino cell has a color that must match at least one adjacent cell, and an integer number of crowns (possibly none) used to compute the score. We prove that even with full knowledge of the future of the game, it is NP -complete to decide whether a given score is achievable at Kingdomino TM. [ABSTRACT FROM AUTHOR]

The complexity of variants of 3 -SAT and Not-All-Equal 3 -SAT is well studied. However, in contrast, very little is known about the complexity of the problems' quantified counterparts. In the first part of this paper, we show that ∀∃ 3 -SAT is Π 2 P -complete even if (1) each variable appears exactly twice unnegated and exactly twice negated, (2) each clause is a disjunction of exactly three distinct variables, and (3) the number of universal variables is equal to the number of existential variables. Furthermore, we show that the problem remains Π 2 P -complete if (1a) each universal variable appears exactly once unnegated and exactly once negated, (1b) each existential variable appears exactly twice unnegated and exactly twice negated, and (2) and (3) remain unchanged. On the other hand, the problem becomes NP-complete for certain variants in which each universal variable appears exactly once. In the second part of the paper, we establish Π 2 P -completeness for ∀∃ Not-All-Equal 3 -SAT even if (1′) the Boolean formula is linear and monotone, (2′) each universal variable appears exactly once and each existential variable appears exactly three times, and (3′) each clause is a disjunction of exactly three distinct variables that contains at most one universal variable. On the positive side, we uncover variants of ∀∃ Not-All-Equal 3 -SAT that are co-NP-complete or solvable in polynomial time. [ABSTRACT FROM AUTHOR]

Glaßer et al. (SIAMJCOMP 2008 and TCS 2009) 2 proved existence of two sparse sets A and B in EXP, where A is 3-tt (truth-table) polynomial-time autoreducible but not weakly polynomial-time Turing mitotic and B is polynomial-time 2-tt autoreducible but not weakly polynomial-time 2-tt mitotic. We unify and strengthen both of those results by showing that there is a sparse set in EXP that is polynomial-time 2-tt autoreducible but not even weakly polynomial-time Turing mitotic. All these results indicate that polynomial-time autoreducibilities in general do not imply polynomial-time mitoticity at all with the only exceptions of the many-one and 1-tt reductions. On the other hand, however, we proved that every autoreducible set for the polynomial-time bounded disjunctive or conjunctive tt reductions is weakly mitotic for the polynomial-time tt reduction that makes logarithmically many queries only. This shows that autoreducible sets for reductions making more than one query could still be mitotic in some way if they possess certain special properties. 2 The two papers have slightly different sets of authors [ABSTRACT FROM AUTHOR]

A total domatic k-partition of a graph is a partition of its vertex set into k subsets such that each intersects the open neighborhood of each vertex. The maximum k for which a total domatic k -partition exists is known as the total domatic number of a graph G , denoted by d t (G). We extend considerably the known hardness results by showing it is Image 1 -complete to decide whether d t (G) ≥ 3 where G is a bipartite planar graph of bounded maximum degree. Similarly, for every k ≥ 3 , it is Image 1 -complete to decide whether d t (G) ≥ k , where G is split or k -regular. In particular, these results complement recent combinatorial results regarding d t (G) on some of these graph classes by showing that the known results are, in a sense, best possible. Finally, for general n -vertex graphs, we show the problem is solvable in 2 n n O (1) time, and derive even faster algorithms for special graph classes. [ABSTRACT FROM AUTHOR]

For each integer m ≥ 2 , every Boolean function f can be expressed as a unique multilinear polynomial modulo m , and the degree of this multilinear polynomial is called its modulo m degree. In this paper we investigate the modulo degree complexity of total Boolean functions initiated by Parikshit Gopalan et al. [9] , in which they asked the following question: whether the degree complexity of a Boolean function is polynomially related with its modulo m degree. For m be a power of primes, it is already known that the module m degree can be arbitrarily smaller compare to the degree complexity (see Section 2 for details). When m has at least two distinct prime factors, the question remains open. Towards this question, our results include: (1) we obtain some nontrivial equivalent forms of this question; (2) we affirm this question for some special classes of functions; (3) we prove a no-go theorem, explaining why this problem is difficult to attack from the computational complexity point of view; (4) we show a super-linear separation between the degree complexity and the modulo m degree. [ABSTRACT FROM AUTHOR]

We consider a simplified version of Not-All-Equal 3- Sat , a variation of the famous Satisfiability problem, where each clause is made up of exactly three distinct literals and the question is whether there exists a truth assignment such that for each clause at least one literal is set to true and at least one is set to false. We show that Not-All-Equal 3- Sat remains NP-complete if (1) each variable appears exactly four times, (2) there are no negations in the formula, and (3) the formula is linear, i.e., each pair of distinct clauses shares at most one variable. Therewith, we improve upon two results in the literature. [ABSTRACT FROM AUTHOR]

Given a set B of d -dimensional boxes (i.e., axis-aligned hyperrectangles), a minimum coverage kernel is a subset of B of minimum size covering the same region as B. Computing it is NP -hard, but as for many similar NP -hard problems (e.g., Box Cover , and Orthogonal Polygon Covering), the problem becomes solvable in polynomial time under restrictions on B. We show that computing minimum coverage kernels remains NP -hard even when restricting the graph induced by the input to a highly constrained class of graphs. Alternatively, we present two polynomial-time approximation algorithms for this problem: one deterministic with an approximation ratio within O (log ⁡ n) , and one randomized with an improved approximation ratio within O (lg ⁡ OPT) (with high probability). [ABSTRACT FROM AUTHOR]

We address questions related to the computational complexity of inferring types for a particular type system, Generic Universe Types (GUT) [1,2] , for Java programs. GUT is useful for many applications, such as program verification [3] , thread synchronization, and memory management. However, requiring the programmer to explicitly provide type information is onerous, which motivates the problem of automatically inferring types. In contrast to classical type systems, ownership type systems such as GUT may have multiple typings that satisfy the type system's rules. It is therefore appropriate for the inference to be tunable — that is, the programmer can indicate preferences for certain typings via breakable constraints and/or by partial annotations. A question then is whether efficient algorithms exist for the type inference problem. In this work we establish the following results for the type inference problem for GUT [2]. (1) The tunable type inference problem that allows breakable constraints is NP -hard, (2) an encoding of the problem as boolean satisfiability (SAT), as in prior work, is indeed a polynomial-time reduction, (3) P ≠ NP implies that the problem is not approximable in polynomial time within an approximation ratio of n 1 − ϵ for any ϵ > 0 , and (4) while some restricted versions of the problem of practical interest, such as when breakable constraints are forbidden, are in P , others remain NP -hard. Our results justify the prior approach to the problem that is based on reduction to SAT. Apart from these results, given the observation in prior work that instances of the problem that arise in practice appear to be easy, we address the natural question as to what hard instances may look like, and whether they may arise in practice. We identify a class of hard instances of the problem by devising a method to generate such instances starting at instances of the Vertex Cover problem, which is known to be NP -hard. We then analyze the structural properties of such instances as compared to easy instances of similar size. We find that for the classes of instances we consider, certain SAT structural parameters may be predictive of empirical hardness. [ABSTRACT FROM AUTHOR]

The (Weighted) Subset Feedback Vertex Set problem is a generalization of the classical Feedback Vertex Set problem and asks for a vertex set of minimum (weight) size that intersects all cycles containing a vertex of a predescribed set of vertices. Although Subset Feedback Vertex Set and Feedback Vertex Set exhibit different computational complexity on split graphs, no similar characterization is known on other classes of graphs. Towards the understanding of the complexity difference between the two problems, it is natural to study the importance of structural graph parameters. Here we consider graphs of bounded independent set number for which it is known that Weighted Feedback Vertex Set can be solved in polynomial time. We provide a dichotomy result with respect to the size α of a maximum independent set. In particular we show that Weighted Subset Feedback Vertex Set can be solved in polynomial time for graphs with α ≤ 3 , whereas we prove that the problem remains NP-hard for graphs with α ≥ 4. Moreover, we show that the (unweighted) Subset Feedback Vertex Set problem can be solved in polynomial time on graphs of bounded independent set number by giving an algorithm with running time n O (α). To complement our results, we demonstrate how our ideas can be extended to other terminal set problems on graphs of bounded independent set size. Node Multiway Cut is a terminal set problem that asks for a vertex set of minimum size that intersects all paths connecting any two terminals. Based on our findings for Subset Feedback Vertex Set , we settle the complexity of Node Multiway Cut as well as its variants where nodes are weighted and/or the terminals are deletable, for every value of the given independent set number. [ABSTRACT FROM AUTHOR]

A classic result of Lenstra [Math. Oper. Res. 1983] says that an integer linear program can be solved in fixed-parameter tractable (FPT) time for the parameterization by the number of variables. We extend this result by incorporating piecewise linear convex or concave functions to our (mixed) integer programs. This general technique allows us to analyze the parameterized complexity of a number of classic NP -hard computational problems. In particular, we prove that Weighted Set Multicover is in FPT when parameterized by the number of elements to cover, and that there exists an FPT -time approximation scheme for Multiset Multicover for the same parameter—this is our most technical result. Further, we use our general technique to prove that a number of problems from computational social choice (e.g., problems related to bribery and control in elections) are in FPT when parameterized by the number of candidates. For bribery, this resolves a nearly 10-year old family of open problems, and for weighted electoral control of Approval voting, this improves some previously known XP -memberships to FPT -memberships. [ABSTRACT FROM AUTHOR]

A semitotal dominating set of a graph G with no isolated vertex is a dominating set D of G such that every vertex in D is within distance two of another vertex in D. The minimum size γ t 2 (G) of a semitotal dominating set of G is squeezed between the domination number γ (G) and the total domination number γ t (G). Semitotal Dominating Set is the problem of finding, given a graph G , a semitotal dominating set of G of size γ t 2 (G). In this paper, we continue the systematic study on the computational complexity of this problem when restricted to special graph classes. In particular, we show that it is solvable in polynomial time for the class of graphs of bounded mim-width by a reduction to Total Dominating Set and we provide several approximation lower bounds for subclasses of subcubic graphs. Moreover, we obtain complexity dichotomies in monogenic classes for the decision versions of Semitotal Dominating Set and Total Dominating Set. Finally, we show that it is NP -complete to recognise the graphs such that γ t 2 (G) = γ t (G) and those such that γ (G) = γ t 2 (G) , even if restricted to be planar and with maximum degree at most 4, and we provide forbidden induced subgraph characterisations for the graphs hereditarily satisfying either of these two equalities. [ABSTRACT FROM AUTHOR]

We show how to represent polynomial time computation in an untyped version of proof-nets for elementary linear logic. This follows previous work by P. Baillot but which was developed in a typed and affine setting. We describe how these two properties can be adapted. [ABSTRACT FROM AUTHOR]

This paper provides an alternate characterization of type-two polynomial-time computability, with the goal of making second-order complexity theory more approachable. We rely on the usual oracle machines to model programs with subroutine calls. In contrast to previous results, the use of higher-order objects as running times is avoided, either explicitly or implicitly. Instead, regular polynomials are used. This is achieved by refining the notion of oracle-polynomial-time introduced by Cook. We impose a further restriction on the oracle interactions to force feasibility. Both the restriction as well as its purpose are very simple: it is well-known that Cook's model allows polynomial depth iteration of functional inputs with no restrictions on size, and thus does not guarantee that polynomial-time computability is preserved. To mend this we restrict the number of lookahead revisions, that is the number of times a query can be asked that is bigger than any of the previous queries. We prove that this leads to a class of feasible functionals and that all feasible problems can be solved within this class if one is allowed to separate a task into efficiently solvable subtasks. Formally put: the closure of our class under lambda-abstraction and application includes all feasible operations. We also revisit the very similar class of strongly polynomial-time computable operators previously introduced by Kawamura and Steinberg. We prove it to be strictly included in our class and, somewhat surprisingly, to have the same closure property. This can be attributed to properties of the limited recursion operator: It is not strongly polynomial-time computable but decomposes into two such operations and lies in our class. [ABSTRACT FROM AUTHOR]

Algebraic Branching Programs (ABPs) are standard models for computing polynomials. Syntactic multilinear ABPs (smABPs) are restrictions of ABPs where every variable is allowed to occur at most once in every path from the source to the sink node. Proving super-polynomial lower bounds for syntactic multilinear ABPs remains a challenging open question in Algebraic Complexity Theory. The current best lower bound for smABPs is only quadratic in the number of variables [1]. In this article, we develop a new approach for proving syntactic multilinear branching program lower bounds: Convert the smABP into an equivalent multilinear formula with a super-polynomial blow-up in size and then exploit the structural limitations of the resulting formula to obtain an upper bound on the rank of partial derivative matrix of the polynomial computed by the smABP. Using this approach, we prove exponential lower bounds for special cases of smABPs namely sum of Read-Once Oblivious smABPs, multilinear r -pass ABPs and α -set-multilinear ABPs. En route, we also prove an exponential lower bound for a special class of syntactic multilinear arithmetic circuits using a similar approach. [ABSTRACT FROM AUTHOR]

Pattern languages have been an object of study in various subfields of computer science for decades. This paper introduces and studies a decision problem on patterns called the finite distinguishability problem: given a pattern π , are there finite sets T + and T − of strings such that the only pattern language containing all strings in T + and none of the strings in T − is the language generated by π ? This problem is related to the complexity of teacher-directed learning, as studied in computational learning theory, as well as to the long-standing open question whether the equivalence of two patterns is decidable. We show that finite distinguishability is decidable if the underlying alphabet is of size other than 2 or 3, and provide a number of related results, such as (i) partial solutions for alphabet sizes 2 and 3, and (ii) decidability proofs for variants of the problem for special subclasses of patterns, namely, regular, 1-variable, and non-cross patterns. For the same subclasses, we further determine the values of two complexity parameters in teacher-directed learning, namely the teaching dimension and the recursive teaching dimension. [ABSTRACT FROM AUTHOR]

This paper introduces Graded Computation Tree Logic with finite path semantics (GCTL f ⁎ , for short), a variant of Computation Tree Logic CTL⁎, in which path quantifiers are interpreted over finite paths and can count the number of such paths. State formulas of GCTL f ⁎ are interpreted over Kripke structures. The syntax of GCTL f ⁎ has path quantifiers of the form E ≥ g ψ which express that there are at least g many distinct finite paths that satisfy ψ. After defining and justifying the logic GCTL f ⁎ , we solve its model checking problem and establish that its computational complexity is PSPACE-complete. Moreover, we investigate GCTL f ⁎ under the imperfect information setting. Precisely, we introduce GCTLK f ⁎ , an epistemic extension of GCTL f ⁎ and prove that the model checking problem also in this case is PSPACE-complete. [ABSTRACT FROM AUTHOR]

We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary operations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration, sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE -completeness of the following decision problems: • Given two satisfying assignments of a planar monotone instance of NAE 3-SAT, can one assignment be transformed into the other by a sequence of variable flips such that the formula remains satisfied at every step? • Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum? • Given two points in { 0 , 1 } n contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n -hypercube connecting the two points and contained in P ? These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the sets of instances that appear as input to the reconfiguration problems in our reductions lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length. [ABSTRACT FROM AUTHOR]

We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal (s , z) -Separation problem is NP -complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph—there we observe polynomial-time solvability in the case of bounded treewidth—as well as restrictions concerning the "temporal evolution" along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases. [ABSTRACT FROM AUTHOR]

Cell-like P systems where communication between the regions are carried out by rules of type symport/antiport are considered. These systems compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves. The environment plays an active role in the sense that it not only can receive objects from the system, but also send objects into it. There is an alphabet associated with the environment whose elements appear in an arbitrary large number of copies at the initial configuration. This property seems too strong from a complexity view, but it has been widely exploited in the design of efficient solutions to computationally hard problems when some mechanisms (inspired by mitosis and membrane fission) allowing to construct an exponential workspace in linear time, are considered. In this paper, complexity aspects of P systems with symport/antiport rules and membrane division are considered when the set associated with the environment is the emptyset. It is shown that the role of the environment is irrelevant for such kind of P systems, in contrast with the well known results concerning to its relevance when membrane separation is used instead of membrane division. [ABSTRACT FROM AUTHOR]

P systems with active membranes is one of the most studied models within the field of Membrane Computing. Simulating the organization and behavior of the living cells through a tree-like structure and abstracting the mechanisms that help the cell to keep alive into rules (evolution, communication, dissolution and division rules), they have been used to solve several computationally hard problems. We are dealing with non-cooperative systems here, that is, the number of reactives in a rule is always one. Even then, it has been proven that problems from the class PSPACE can be solved, so in order to acquire a minimal model that can solve computationally hard problems, polarizations are removed. In this paper we find the relevance of the length of the right-hand side of the rule, being necessary when using separation rules and being irrelevant when division rules are used, improving some solutions previously presented, restricting the right-hand side of the rules, obtaining new frontiers of efficiency in this framework. The state of the art of these systems is presented in a graphical way. [ABSTRACT FROM AUTHOR]

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of Cyclic Level Planarity and Torus Level Planarity , are polynomial-time solvable. Moreover, we show a complexity dichotomy for testing the Simultaneous Level Planarity of a set of level graphs, with respect to both the number of level graphs and the number of levels. [ABSTRACT FROM AUTHOR]

A set of vertices S of a graph G is geodesically convex if for every pair of vertices of S , all vertices of all shortest paths joining them also lie in S. The geodetic convex hull of S , denoted by 〈 S 〉 , is the minimum geodesically convex set of G containing S. We say that S is Carathéodory independent if 〈 S 〉 ∖ (⋃ a ∈ S 〈 S ∖ { a } 〉) ≠ ∅ and that S is exchange independent if | S | = 1 or there is p ∈ S such that 〈 S ∖ { p } 〉 ∖ ⋃ a ∈ S ∖ { p } 〈 S ∖ { a } 〉 ≠ ∅. The Carathéodory number (exchange number) of G is the cardinality of a maximum Carathéodory (exchange) independent set. In this paper, we show that deciding whether a given graph has exchange number at most k is an NP -complete problem. We also present characterizations of the Carathéodory and exchange numbers for some graph classes, like unit interval graphs and powers of cycles, which allow us to determine these parameters in polynomial time. [ABSTRACT FROM AUTHOR]

A mixed shop is a manufacturing infrastructure designed to process a mixture of a set of flow-shop jobs and a set of open-shop jobs. Mixed shops are in general much more complex to schedule than flow-shops and open-shops, and have been studied since the 1980's. We consider the three machine proportionate mixed shop problem denoted as M 3 | p r p t | C max , in which by "proportionate" each job has equal processing times on all three machines. Koulamas and Kyparisis (2015) [6] showed that the problem is solvable in polynomial time in some very special cases; for the non-solvable case, they proposed a 5/3-approximation algorithm. In this paper, we first present an improved 4/3-approximation algorithm and show that this ratio of 4/3 is asymptotically tight; when the largest job is a flow-shop job, we then present a fully polynomial-time approximation scheme (FPTAS). On the negative side, while the F 3 | p r p t | C max problem is polynomial-time solvable, we show an interesting hardness result that adding one open-shop job to the job set makes the problem NP-hard if this open-shop job is larger than any flow-shop job. We are able to design an FPTAS for this special case too. [ABSTRACT FROM AUTHOR]

We consider the one-variable fragment of first-order logic extended with Presburger constraints. The logic is designed in such a way that it subsumes the previously-known fragments extended with counting, modulo counting or cardinality comparison and combines their expressive powers. We prove Image 1 -completeness of the logic by presenting an optimal algorithm for solving its finite satisfiability problem. [ABSTRACT FROM AUTHOR]

This paper concerns the question to what extent it can be efficiently determined whether an arbitrary program correctly solves a given problem. This question is investigated with programs of a very simple form, namely instruction sequences, and a very simple problem, namely the non-zeroness test on natural numbers. The instruction sequences concerned are of a kind by which, for each n > 0 , each function from { 0 , 1 } n to { 0 , 1 } can be computed. The established results include the time complexities of the problem of determining whether an arbitrary instruction sequence correctly implements the restriction to { 0 , 1 } n of the function from { 0 , 1 } ⁎ to { 0 , 1 } that models the non-zeroness test function, for n > 0 , under several restrictions on the arbitrary instruction sequence. [ABSTRACT FROM AUTHOR]

We investigate the computational complexity of balance problems for { ∖ , ⋅ } -circuits computing finite sets of natural numbers. These problems naturally build on problems for integer expressions and integer circuits studied by Stockmeyer and Meyer (1973), McKenzie and Wagner (2007), and Glaßer et al. (2010). Our work shows that the balance problem for { ∖ , ⋅ } -circuits is undecidable which is the first natural problem for integer circuits or related constraint satisfaction problems that admits only one arithmetic operation and is proven to be undecidable. Starting from this result we precisely characterize the complexity of balance problems for proper subsets of { ∖ , ⋅ }. These problems turn out to be complete for one of the classes L, NL, and NP. [ABSTRACT FROM AUTHOR]

Inspired by scaffold filling, a recent approach for genome reconstruction from incomplete data, we consider a variant of the well-known longest common subsequence problem for the comparison of two sequences. The new problem, called Longest Filled Common Subsequence, aims to compare a complete sequence with an incomplete one, i.e. with some missing elements. Longest Filled Common Subsequence (LFCS), given a complete sequence A , an incomplete sequence B , and a multiset M of symbols missing in B , asks for a sequence B ⁎ obtained by inserting the symbols of M into B so that B ⁎ induces a common subsequence with A of maximum length. We investigate the computational and approximation complexity of the problem and we show that it is NP-hard and APX-hard when A contains at most two occurrences of each symbol, and we give a polynomial time algorithm when the input sequences are over a constant-size alphabet. We give a 3 5 − approximation algorithm for the Longest Filled Common Subsequence problem. Finally, we present a fixed-parameter algorithm for the problem, when it is parameterized by the number of symbols inserted in B that "match" symbols of A. [ABSTRACT FROM AUTHOR]

We study the combinatorial FIFO Stack-Up problem. In the delivery industry, bins have to be moved from conveyor belts onto pallets. Given is a list Q of k sequences of labeled bins and a positive integer p. The goal is to palletize the bins by iteratively removing the first bin of one of the k sequences and putting it onto a pallet located at one of p stack-up places. Each of these pallets has to contain bins of only one label, bins of different labels have to be placed on different pallets. After all bins of one label have been removed from the given sequences, the corresponding stack-up place becomes available for a pallet of bins of another label. The FIFO Stack-Up problem asks whether such a processing is possible. The FIFO Stack-Up problem is known to be NP-complete even if the sequences of Q contain together at most c Q = 6 bins per pallet. This implies that the problem is also hard if all bins of every pallet are distributed to at most d Q = 6 sequences. In this paper we strengthen the hardness to the cases c Q = 5 and d Q = 3. We also show the hardness for the practical case where the number of sequences is smaller than the number of pallets, and we point out differences to related problems like 3D Bin Packing and Train Marshalling. [ABSTRACT FROM AUTHOR]

The game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in "Pursuing a fast robber on a graph", generalizing a well-known game of Cops and Robber which has robber speed 1. We answer their open question about the computational complexity of the game on interval graphs with ∞-fast robber, showing it to be polynomially decidable. We also generalize the concept of k -defensive domination introduced by Farley and Proskurowski in "Defensive Domination" to A -defensive domination and use it as a main tool in our proof. The generalization allows specifying arbitrary attacks and limiting the number of defenders of each vertex. While this problem is NP-complete even for split graphs, we show that A -defensive domination is decidable in polynomial time on interval graphs. [ABSTRACT FROM AUTHOR]

Let P be a polygon with r > 0 reflex vertices and possibly with holes and islands (i.e., components of the polygon inside holes). A subsuming polygon of P is a polygon P ′ such that P ⊆ P ′ , each connected component R of P is a subset of a distinct connected component R ′ of P ′ , and the reflex corners of R coincide with those of R ′. A subsuming chain of P ′ is a minimal path on the boundary of P ′ whose two end edges coincide with two edges of P. Aichholzer et al. proved that every polygon P has a subsuming polygon with O (r) vertices, and posed an open problem to determine the computational complexity of computing subsuming polygons with the minimum number of convex vertices. In this paper, we prove that the problem of computing an optimal subsuming polygon is NP-hard (but the complexity remains open for simple polygons; i.e., polygons without holes). Our NP-hardness result holds even when the subsuming chains are restricted to have constant length and lie on the arrangement of lines determined by the edges of the input polygon. We show that this restriction makes the problem polynomial-time solvable for simple polygons. [ABSTRACT FROM AUTHOR]

Gerrymandering is a long-standing issue within the U.S. political system, and it has received scrutiny recently by the U.S. Supreme Court. In this note, we prove that deciding whether there exists a fair redistricting among legal maps is NP -hard. To make this precise, we use simplified notions of "legal" and "fair" that account for desirable traits such as geographic compactness of districts and sufficient representation of voters. The proof of our result is inspired by the work of Mahanjan, Minbhorkar and Varadarajan that proves that planar k -means is NP -hard. [ABSTRACT FROM AUTHOR]

We study the computational complexity of various problems related to synchronization of weakly acyclic automata, a subclass of widely studied aperiodic automata. We provide upper and lower bounds on the length of a shortest word synchronizing a weakly acyclic automaton or, more generally, a subset of its states, and show that the problem of approximating this length is hard. We investigate the complexity of finding a synchronizable set of states of maximum size. We also show inapproximability of the problem of computing the rank of a subset of states in a binary weakly acyclic automaton and prove that several problems related to recognizing a synchronizable subset of states in such automata are NP-complete. [ABSTRACT FROM AUTHOR]

In a combinatorial search problem we wish to identify an unknown element by binary tests, where the edges of a hypergraph specify the available tests. We show that, for rather general cases of this problem, the worst-case minimum number of tests, even if adaptive testing is permitted, can already be achieved in a small number of rounds of parallel tests. In particular, the maximum number of necessary rounds grows only as the square root of the number of elements, and two rounds are enough if, e.g., the test number is close to the number of elements, or the hypergraph is a graph. We also provide polynomial-time, hardness, and parameterized results on the computational complexity of finding optimal strategies for some cases, including graphs and tree hypergraphs. • We study multi-round combinatorial search on test hypergraphs in full generality. • We show a tight bound on the number of rounds needed for the optimal test number. • In several natural cases, strategies with optimal test number need only two rounds. • Related computational problems are NP-hard but fixed-parameter tractable. • The case of graphs can be completely solved in polynomial time. [ABSTRACT FROM AUTHOR]

The search for new mechanisms and tools allowing us to tackle the famous P versus NP problem from new perspectives is an important task, due to the relevance of that problem. The concept of efficiency of computing models is associated with the ability to solve intractable (in a classical sense) problems in polynomial time. Assuming that P ≠ NP , that concept is equivalent to the capability to solve NP -complete problems in an efficient way. Different frontiers of the efficiency have been given in Membrane Computing in terms of syntactical or semantic ingredients of the models. In particular, in the framework of tissue P systems with cell division using symport/antiport rules, the length of communication rules (passing from length 1 to length 2) provides an optimal borderline of the efficiency. Cell-like P systems with symport/antiport rules and membrane division is a restricted variant of such tissue P systems in both its structure (rooted tree versus undirected graph) and in the way membranes communicate with each other and with the environment. The limitations of efficient computations in such kind of P systems which use non-cooperative communication rules have been previously established. In this paper, a uniform polynomial time solution for the Hamiltonian cycle problem , a well known NP -complete problem, by means of cell-like P systems with membrane division using minimal cooperation in communication rules (at most two objects are involved), is provided. Hence, a new optimal boundary between tractability and NP -hardness, is provided: passing from non-cooperative rules to cooperative rules in cell-like P systems with symport/antiport rules and membrane division amounts to passing from non-efficiency to efficiency. [ABSTRACT FROM AUTHOR]

Question-answering systems like Watson beat humans when it comes to processing speed and memory. But what happens if we compensate for this? What are the fundamental differences in power between human and artificial agents in question answering? We explore this issue by defining new computational models for both agents and comparing their computational efficiency in interactive sessions. Concretely, human agents are modeled by means of cognitive automata , augmented with a form of background intelligence which gives the automata the possibility to query a given Turing machine and use the answers from one interaction to the next. On the other hand, artificial question-answering agents are modeled by QA-machines , which are Turing machines that can access a predefined, potentially infinite knowledge base ('advice') and have a bounded amount of learning space at their disposal. We show that cognitive automata and QA-machines have exactly the same potential in realizing question-answering sessions, provided the resource bounds in one model are sufficient to match the abilities of the other. In particular, polynomially bounded cognitive automata with background intelligence (i.e. human agents) prove to be equivalent to polynomially bounded QA-machines with logarithmic learning space. It generalizes Pippenger's theorem on the computational power of switching circuits (without background intelligence) to a foundational result for question answering in cognitive science. The framework reveals why QA-machines have a fundamental advantage. [ABSTRACT FROM AUTHOR]

With the arrival of modern internet era, large public networks of various types have come to existence to benefit the society as a whole and several research areas such as sociology, economics and geography in particular. However, the societal and research benefits of these networks have also given rise to potentially significant privacy issues in the sense that malicious entities may violate the privacy of the users of such a network by analyzing the network and deliberately using such privacy violations for deleterious purposes. Such considerations have given rise to a new active research area that deals with the quantification of privacy of users in large networks and the corresponding investigation of computational complexity issues of computing such quantified privacy measures. In this paper, we formalize three natural problems related to such a privacy measure for large networks and provide non-trivial theoretical computational complexity results for solving these problems. Our results show the first two problems can be solved efficiently, whereas the third problem is provably hard to solve within a logarithmic approximation factor. Furthermore, we also provide computational complexity results for the case when the privacy requirement of the network is severely restricted, including an efficient logarithmic approximation. [ABSTRACT FROM AUTHOR]

A solution extension problem consists in an instance and a partial feasible solution which is given in advance and the goal is to extend this partial solution to a feasible one. Many well-known problems like Coloring Extension Problems, Traveling Salesman Problem and Routing problems, have been studied in this framework. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP -hardness, parameterized complexity, positive and negative approximation results. • An extension variant of the weighted edge cover problem is studied. • The problem is NP -complete in complete graphs while polynomial solvable in bounded tree-width graphs. • For non-negative weights, the minimization version is in-approximable at all while the maximization version is in RAPX. • If weight function satisfies (extended) c -relaxed triangle inequalities, the minimization version is in RAPX. [ABSTRACT FROM AUTHOR]

Abstract Given a simple graph G , a weight function w : E (G) → N ∖ { 0 } , and an orientation D of G , we define μ − (D) = max v ∈ V (G) ⁡ w D − (v) , where w D − (v) = ∑ u ∈ N D − (v) w (u v). We say that D is a weighted proper orientation of G if w D − (u) ≠ w D − (v) whenever u and v are adjacent. We introduce the parameter weighted proper orientation number of G , denoted by χ → (G , w) , which is the minimum, over all weighted proper orientations D of G , of μ − (D). When all the weights are equal to 1, this parameter is equal to the proper orientation number of G , which has been object of recent studies and whose determination is NP -hard in general, but polynomial-time solvable on trees. Here, we prove that the equivalent decision problem of the weighted proper orientation number (i.e., χ → (G , w) ≤ k ?) is (weakly) NP -complete on trees but can be solved by a pseudo-polynomial time algorithm whose running time depends on k. Furthermore, we present a dynamic programming algorithm to determine whether a general graph G on n vertices and treewidth at most tw satisfies χ → (G , w) ≤ k , running in time O (2 tw 2 ⋅ k 3 tw ⋅ tw ⋅ n) , and we complement this result by showing that the problem is W [ 1 ] -hard on general graphs parameterized by the treewidth of G , even if the weights are polynomial in n. [ABSTRACT FROM AUTHOR]

Abstract In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete even when restricted to bipartite graphs. It has been proved that Matching Cut is polynomially solvable for graphs of diameter two. In this paper, we show that, for any fixed integer d ≥ 3 , Matching Cut is NP -complete in the class of graphs of diameter d. This resolves an open problem posed by Borowiecki and Jesse-Józefczyk (2008) [6]. We then show that, for any fixed integer d ≥ 4 , Matching Cut is NP -complete even when restricted to the class of bipartite graphs of diameter d. Complementing the hardness results, we show that Matching Cut is polynomial-time solvable in the class of bipartite graphs of diameter at most three, and point out a new and simple polynomial-time algorithm solving Matching Cut in graphs of diameter 2. [ABSTRACT FROM AUTHOR]

Abstract We show that for several pattern graphs on four vertices (e.g., C 4), their induced copies in host graphs with n vertices and no clique on k + 1 vertices can be deterministically detected in O (n 2.5719 k 0.3176 + n 2 k 2) time for k < n 0.394 and O (n 2.5 k 0.5 + n 2 k 2) time for k ≥ n 0.394. The aforementioned pattern graphs have a pair of non-adjacent vertices whose neighborhoods are equal. By considering dual graphs, in the same asymptotic time, we can also detect four vertex pattern graphs, that have an adjacent pair of vertices with the same neighbors among the remaining vertices (e.g., K 4), in host graphs with n vertices and no independent set on k + 1 vertices. By using the concept of Ramsey numbers, we can extend our method for induced subgraph isomorphism to include larger pattern graphs having a set of independent vertices with the same neighborhood and n -vertex host graphs without cliques on k + 1 vertices (as well as the pattern graphs and host graphs dual to the aforementioned ones, respectively). [ABSTRACT FROM AUTHOR]

Highlights • Algorithms for covering and hitting a given set of line segments by two congruent squares of minimum size is studied. • The algorithm produces optimum solution by sequentially reading the input array (read only) twice. • The extra space complexity of the algorithm is O (1). • A restricted version of covering is also studied where each object is to be completely covered by at least one square. • This algorithm gives 2 approximation result to cover/hit the segments with two congruent disks of minimum size. Abstract This paper discusses the problem of covering and hitting a set of line segments L in R 2 by a pair of axis-parallel congruent squares of minimum size. We also discuss the restricted version of covering, where each line segment in L is to be covered completely by at least one square. The proposed algorithms assume that the input segments are given in a read-only array. For each of these problems (i.e. covering , hitting and restricted covering problems), our proposed algorithm reports the optimum result by executing only two passes of reading the input array sequentially. All these algorithms need only O (1) extra space. The solution of these problems also give a 2 approximation for covering and hitting those line segments L by two congruent disks of minimum radius with same computational complexity. [ABSTRACT FROM AUTHOR]

Abstract Consider a user who needs to perform computation over an initially unbounded stream of input. The user would like to compute functions of the input that change dynamically due to external events. The focus of this work is outsourcing such computation to a set of agents. The outsourcing must meet several constraints. Any large enough subset of agents must correctly emulate the user's computation on the unbounded stream of input. Any small subset of agents must obtain as little information as possible on the user's data, including the computed functions and any initial input. This privacy assurance must be maintained in an information-theoretic sense. Finally, the set of agents is dynamic with agents joining and leaving the set and different sets of agents being merged , cloned or split. In this work, we show how to securely outsource such perennial computation. The user's required computation is modeled as programs for a universal Turing machine. The only information that the agents obtain on the user's secrets is an upper bound on the space complexity required to perform the computation. Each state transition of the user's Turing machine requires computation and communication that are linear in the Turing machine's space complexity and polynomial in the number of agents performing the computation for every round of computation. The communication and computational complexity for an agent joining or leaving the set of computing agents in a transition round are linear in the space complexity of the Turing machine and polynomial in the number of agents. Some of the tools we develop may be of independent interest. We construct a strongly oblivious Turing machine, in which the tape head moves only as a function of its current location. We also show how to securely share the description of a Turing machine among several agents and how to securely compute each Turing machine's transition in a constant number of communication rounds. [ABSTRACT FROM AUTHOR]

Highlights • Study the all-terminal reliability of planar networks as a measure of the network invulnerability. • Give the new polynomial algorithm for calculating the reliability of planar two-connected networks. • Determine the corresponding uniformly-most reliable networks and uniformly-worst reliable networks. Abstract Let us model the network by an undirected graph G , in which each edge fails independently with probability q ∈ [ 0 , 1 ] , the all-terminal reliability of the network is the probability that the graph G remains connected and it is one of the important measure for the invulnerability of the network. Clearly, the all-terminal reliability can be written as a polynomial in either q. Theoretically, it has been proved that calculating all-terminal reliability for planar networks is # P -complete. Up now we cannot find any results for some special classes of the planar networks. This paper studies the all-terminal reliability of the two-tree networks and its generalizations. A linear algorithm for calculating the reliability of a planar two-tree networks is proposed, with algorithmic complexity O (n) , where n is the number of steps. Then both the uniformly-most reliable network model and the uniformly-worst reliable network model are determined by using the algorithm. Finally, a polynomial algorithm for planar two-connected networks is proposed based on an expended algorithm and the corresponding uniformly-most reliable network model and uniformly-worst reliable network model are also presented, with computational complexity O (n) , where n is the number of steps. [ABSTRACT FROM AUTHOR]

Abstract A Boolean Finite Synchronous Dynamical System (BFDS, for short) consists of a finite number of objects that each maintains a boolean state, where after individually receiving state assignments, the objects update their state with respect to object-specific time-independent boolean functions synchronously in discrete time steps. The present paper studies the computational complexity of determining, given a boolean finite synchronous dynamical system, a configuration, which is a boolean vector representing the states of the objects, and a positive integer t , whether there exists another configuration from which the given configuration can be reached in t steps. It was previously shown that this problem, which we call the t -Predecessor Problem, is NP-complete even for t = 1 if the update function of an object is either the conjunction of arbitrary fan-in or the disjunction of arbitrary fan-in. This paper studies the computational complexity of the t -Predecessor Problem for a variety of sets of permissible update functions as well as for polynomially bounded t. It also studies the t -Garden-Of-Eden Problem, a variant of the t -Predecessor Problem that asks whether a configuration has a t -predecessor, which itself has no predecessor. The paper obtains complexity theoretical characterizations of all but one of these problems. [ABSTRACT FROM AUTHOR]

Abstract W.O. Krawec (2012) [17] introduced a method of analyzing multi-player impartial games, and derived a recursive function capable of determining which of the n players has a winning strategy. The present paper is devoted to "Multi-player End-Nim games", abbreviated by ENim(N , n), assuming that the standard alliance matrix is adopted. The game values of ENim(N , n) are completely determined for three cases n > N + 1 , n = N + 1 and n = N. For the case n < N , by letting d = N − n ≥ 1 , the game values of ENim(n + d , n) are completely determined if n ≥ d + 4. The case 3 ≤ n ≤ d + 3 is more complicated, we present the game values for d = 1. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we address the Approximate Agreement problem in the Mobile Byzantine Fault model. Our contribution is three-fold. First, we refine the problem specification to adapt it to the Mobile Byzantine Fault environment. Then, we propose the first mapping from the existing variants of Mobile Byzantine models to the Mixed-mode Fault model. This mapping further help us to prove the correctness of MSR (Mean-Subsequence-Reduce) algorithms class in our context and it is of independent interest. We also prove lower bounds for solving Approximate Agreement under all existing Mobile Byzantine fault models. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we give the first polynomial time algorithm to compute the generalized Hermite normal form for a matrix F over Z [ x ] , or equivalently, the reduced Gröbner basis of the Z [ x ] -module generated by the column vectors of F. The algorithm has polynomial bit size computational complexities and is also shown to be practically more efficient than existing algorithms. The algorithm is based on three key ingredients. First, an F4 style algorithm to compute the Gröbner basis is adopted, where a novel prolongation is designed such that the sizes of coefficient matrices under consideration are nicely controlled. Second, the complexity bound of the algorithm is achieved by a nice estimation for the degree and height bounds of the polynomials in the generalized Hermite normal form. Third, fast algorithms to compute Hermite normal forms of matrices over Z are used as the computational tool. [ABSTRACT FROM AUTHOR]

Abstract The significant increase in the number of processors of the multiprocessor system increases its vulnerability to component failures. Diagnosability is an important indicator in measuring the reliability of interconnection networks. The g -good-neighbor conditional faulty set is a faulty set that each fault-free vertex is adjacent to at least g fault-free vertices. The g -good-neighbor conditional diagnosability gives the maximum cardinality of g -good-neighbor conditional faulty set that the system is guaranteed to identify. This paper we establish the g -good-neighbor conditional diagnosability of the crossed cube C Q n under the PMC and MM* model. [ABSTRACT FROM AUTHOR]