Hashiwokakero is NP-complete

In a Hashiwokakero puzzle, one must build bridges to connect a set of islands. We show that deciding the solvability of such puzzles is NP-complete.     

A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs

An edge ranking of a graph G is a labeling r of its edges with positive integers such that every path between two different edges eu, ev with the same rank r(eu)=r(ev) contains an intermediate edge ew with rank r(ew)>r(eu). An edge ranking of G is minimum if the largest rank k assigned is the smallest among all rankings of G. The edge ranking problem is to find a minimum edge ranking of given graph G. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of trees. In this paper, we first show, on a general graph G, a relation between a minimum edge ranking of G and its minimal cuts, which ensures that we can obtain a polynomial time algorithm for obtaining minimum edge ranking of a given graph G if minimal cuts for each subgraph of G can be found in polynomial time and the number of those is polynomial. Based on this relation, we develop a polynomial time algorithm for finding a minimum edge ranking on a 2-connected outerplanar graph.     

Computing sparse permanents faster

Bax and Franklin (2002) gave a randomized algorithm for exactly computing the permanent of any n×n zero-one matrix in expected time exp[−Ω(n1/3/(2lnn))]n². Building on their work, we show that for any constant C>0 there is a constant ?>0 such that the permanent of any n×n (real or complex) matrix with at most Cn nonzero entries can be computed in deterministic time n(2−?) and space O(n). This improves on the Ω(n²) runtime of Ryser's algorithm for computing the permanent of an arbitrary real or complex matrix.     

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.     

The complexity of changing colourings with bounded maximum degree

Let G be a graph, x,y∈V(G), and ?:V(G)→[k] a k-colouring of G such that ?(x)=?(y). If then the following question is NP-complete: Does there exist a k-colouring ?^′ of G such that ?^′(x)≠?^′(y)? Conversely, if then the problem is polynomial time.     

Rigidity of a simple extended lower triangular matrix

For the all-ones lower triangular matrices, the upper and lower bounds on rigidity are known to match [P. Pudlak, Z. Vavrin, Computation of rigidity of order n²/r for one simple matrix, Comment Math. Univ. Carolin. 32 (2) (1991) 213-218]. In this short note, we apply these techniques to the all-ones extended lower triangular matrices, to obtain upper and lower bounds with a small gap between the two; we show that the rigidity is .     

Complexities of some interesting problems on spanning trees

This paper deals with the complexity issues of some new interesting spanning tree problems. Here we define some new spanning tree problems by imposing various constraints and restrictions on graph parameters and present relevant results. Also we introduce a new notion of “set version” of some decision problems having integer K<|V| as a parameter in the input instance, where we replace K by a set X⊆|V|. For example, the set version of Maximum Leaf Spanning Tree problem asks whether there exists a spanning tree in G that contains X as a subset of the leaf set. We raise the issue of whether the set versions of NP-complete problems are as hard as the original problems and prove that although in some cases the set versions are easier to solve, this is not necessarily true in general.     

Sensitivity versus block sensitivity of Boolean functions

Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with . The best known separation previously was due to Rubinstein. We also report results of computer search for functions with at most 13 variables.     

The cycle roommates problem: a hard case of kidney exchange

Recently, a number of interesting algorithmic problems have arisen from the emergence, in a number of countries, of kidney exchange schemes, whereby live donors are matched with recipients according to compatibility and other considerations. One such problem can be modeled by a variant of the well-known stable roommates problem in which blocking cycles, as well as the normal blocking pairs, are significant. We show here that this variant of the stable roommates problem is NP-complete, thus solving an open question posed by Cechlárová and Lacko.     

Bases for Boolean co-clones

The complexity of various problems in connection with Boolean constraints, like, for example, quantified Boolean constraint satisfaction, have been studied recently. Depending on what types of constraints may be used, the complexity of such problems varies. A very interesting observation of the recent past has been that the thus derived classification of constraints can be explained with the help of universal algebra. More precisely, the difficulty of such a constraint problem often depends on the co-clone the constraints are from. A co-clone is a set of Boolean relations that is closed under very natural closure operations. Nearly all these co-clones can be generated by said operators out of a finite set of relations, a so-called base. Knowing a, preferably simple, base for each co-clone can therefore be of great value when studying the complexity of Boolean constraint problems, since this knowledge reduces the infinitely many cases of equivalent problems to a single one—the constraint satisfaction problem for this base. In this paper we give a finite and simple base for every Boolean co-clone, where this is possible. We give evidence that the presented bases are as easy as possible.     

Complexity of question/answer games

Question/Answer games (Q/A games for short) are a generalization of the Rényi–Ulam game and they are a model for information extraction in parallel. A Q/A game, G=(D,s,(_q1,…,_qk))$G=(D,s,(q_1,\dots ,q_k))$, is played on a directed acyclic graph, D=(V,E)$D=(V,E)$, with a distinguished start vertex s$s$. In the i$i$th round, Paul selects a set, _Qi⊆V$Q_i\subseteq V$, of at most _qi$q_i$ non-terminal vertices. Carole responds by choosing an outgoing edge from each vertex in _Qi$Q_i$. At the end of k$k$ rounds, Paul wins if Carole’s answers define a unique path from the root to one of the terminal vertices in D$D$.     

On the approximability of minmax (regret) network optimization problems

In this paper the minmax (regret) versions of some basic polynomially solvable deterministic network problems are discussed. It is shown that if the number of scenarios is unbounded, then the problems under consideration are not approximable within log1−?K for any ?>0 unless NP⊆DTIME(npolylogn), where K is the number of scenarios.     

Tractability frontiers of the partner units configuration problem

The partner units problem (PUP) is an acknowledged hard benchmark problem for the Logic Programming community with various industrial application fields like surveillance, electrical engineering, computer networks or railway safety systems. Although it is already known for a while that the PUP is NP-complete in its general form, complexity for subproblems reflecting the real problems in industrial fields remained widely unclear so far. In this article we provide all missing complexity results. For the subclass of the PUP that belongs to the complexity class P we present a polynomial-time algorithm and give in-depth algorithmic complexity results.     

Parameterized complexity of the induced subgraph problem in directed graphs

In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is W[1]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs.     

On finding cycle bases and fundamental cycle bases with a shortest maximal cycle

An undirected biconnected graph G with nonnegative integer lengths on the edges is given. The problem we consider is that of finding a cycle basis B of G such that the length of the longest cycle included in B is the smallest among all cycle bases of G. We first observe that Horton's algorithm [SIAM J. Comput. 16 (2) (1987) 358-366] provides a fast solution of the problem that extends the one given by Chickering et al. [Inform. Process. Lett. 54 (1995) 55-58] for uniform graphs. On the other hand we show that, if the basis is required to be fundamental, then the problem is NP-hard and cannot be approximated within 2−?, ∀?>0, even with uniform lengths, unless P=NP. This problem remains NP-hard even restricted to the class of complete graphs; in this case it cannot be approximated within 13/11−?, ∀?>0, unless P=NP; it is instead approximable within 2 in general, and within 3/2 if the triangle inequality holds.