On the complexity of graph self-assembly in accretive systems

We study the complexity of the Accretive Graph Assembly Problem (). An instance of consists of an edge-weighted graph G, a seed vertex in G, and a temperature τ. The goal is to determine if the graph G can be assembled by a sequence of vertex additions starting from the seed vertex. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature. A vertex can be added when the total weight to its already built neighbors in the graph is at least τ. The assembly process is sequential meaning that only one vertex can be added at a time. Our first result is that is NP-complete even on planar graphs with maximum degree 3 when edges have only two different types of weights. This resolves the complexity of in the sense that the problem is poly-time solvable when either the maximum degree is at most 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of on graphs with maximum degree 3 and two distinct weights: w _p and w _n . We give a simple system of linear constraints on w _p , w _n , and τ that determines whether the problem is NP-complete or is poly-time solvable. In the process of establishing this dichotomy, we give a poly-time algorithm to solve a non-trivial class of Finally, we consider the optimization version of where the goal is to assemble a largest-possible induced subgraph of the given input graph. We show that even on graphs that can be assembled and have maximum degree 3, it is NP-hard to assemble a (1/n ^1-ε)-fraction of the input graph for any here n denotes the number of vertices in G.     

The communication complexity of the Hamming distance problem

We investigate the randomized and quantum communication complexity of the Hamming Distance problem, which is to determine if the Hamming distance between two n-bit strings is no less than a threshold d. We prove a quantum lower bound of Ω(d) qubits in the general interactive model with shared prior entanglement. We also construct a classical protocol of O(dlogd) bits in the restricted Simultaneous Message Passing model with public random coins, improving previous protocols of O(d²) bits [A.C.-C. Yao, On the power of quantum fingerprinting, in: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 77-81], and O(dlogn) bits [D. Gavinsky, J. Kempe, R. de Wolf, Quantum communication cannot simulate a public coin, quant-ph/0411051, 2004].     

The quantum query complexity of the determinant

In this paper we give tight quantum query complexity bounds of some important linear algebra problems. We prove Θ(n²) quantum query bounds for verify the determinant, rank, matrix inverse and the matrix power problem.     

The parameterized complexity of probability amplification

In this paper we study the parameterized complexity of probability amplification for some parameterized probabilistic classes. We prove that it is very unlikely that W[P] has the probability amplification property.     

The complexity of propositional implication

The question whether a set of formulae Γ implies a formula φ is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae that are built from a systematically restricted set of Boolean connectives. We give a complete complexity-theoretic classification for all sets of Boolean functions in the meaning of Post's lattice and show that the implication problem is efficiently solvable only if the connectives are definable using the constants {0,1} and only one of {∧,∨,⊕}. The problem remains coNP-complete in all other cases. We also consider the restriction of Γ to singletons which makes the problem strictly easier in some cases.     

The complexity of the certification of properties of Stable Marriage

We give some lower bounds on the certificate complexity of some problems concerning stable marriage, answering a question of Gusfield and Irving.     

On the P versus NP intersected with co-NP question in communication complexity

We consider the analog of the P versus NP∩co-NP question for the classical two-party communication protocols where polynomial time is replaced by poly-logarithmic communication: if both a boolean function f and its negation ¬f have small (poly-logarithmic in the number of variables) nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition model of communication this question was answered by Aho, Ullman and Yannakakis in 1983: here P=NP∩co-NP.We show that in the best partition model of communication the situation is entirely different: here P is a proper subset even of RP∩co-RP. This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982.     

Finding next-to-shortest paths in a graph

We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. In contrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem.     

The computational complexity of ideal semantics

We analyse the computational complexity of the recently proposed ideal semantics within both abstract argumentation frameworks (afs) and assumption-based argumentation frameworks (abfs). It is shown that while typically less tractable than credulous admissibi-lity semantics, the natural decision problems arising with this extension-based model can, perhaps surprisingly, be decided more efficiently than sceptical preferred semantics. In particular the task of finding the unique ideal extension is easier than that of deciding if a given argument is accepted under the sceptical semantics. We provide efficient algorithmic approaches for the class of bipartite argumentation frameworks and, finally, present a number of technical results which offer strong indications that typical problems in ideal argumentation are complete for the class of languages decidable by polynomial time algorithms allowed to make non-adaptive queries to a C oracle, where C is an upper bound on the computational complexity of deciding credulous acceptance: C=np for afs and logic programming (lp) instantiations of abfs; for abfs modelling default theories.     

Computational complexity of the advancing front triangulation

An attempt to reduce the computational complexity of the advancing front triangulation is described. The method is first decomposed into subtasks, and the computational complexity is investigated separately for them. It is shown that a major subtask, namely the geometric ompatibility (mesh correctness) checks can be carried out with linear growth rate. The applied techniques include modified advancing front management, and a localization device in the form of a regular grid (stored as a hypermatrix). The other subtask (access to mesh control function) could not be made of linear computational complexity for all modes of mesh control (ad hoc and adaptive). While thead hoc gradation control yields an algorithm with ideal oveall computational complexity, the adaptive gradation control gives still a suboptimal complexity (of orderO(N logN)).     

Parameterized power domination complexity

The optimization problem of measuring all nodes in an electrical network by placing as few measurement units (PMUs) as possible is known as Power Dominating Set. Nodes can be measured indirectly according to Kirchhoff's law. We show that this problem can be solved in linear time for graphs of bounded treewidth and establish bounds on its parameterized complexity if the number of PMUs is the parameter.     

Complexity analysis of a decentralised graph colouring algorithm

Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks.     

On the complexity of one-shot translational separability

The problem of deciding whether 2- or 3-dimensional objects can be separated by a sequence of arbitrary translational motions is known to have exponential lower bounds. However, under certain restrictions on the type of motions, polynomial time bounds have been shown. An example is finding a subset of the parts that is removable by a single translation. In this case, the main restriction is that all selected parts are required to be removed in the same direction and with the same velocity. It was an open question whether the polynomial time bound can be achieved if more than a single velocity is allowed for the moving parts. In this paper, we answer this question by proving that such ‘multi-handed’ separability problems are NP-hard.