Graph canonization is the problem of computing a unique

representative, a canon, from the isomorphism class of a given graph. This

implies that two graphs are isomorphic exactly if their canons are equal. We

show that graphs of bounded tree width can be canonized by logarithmic-space

(logspace) algorithms. This implies that the isomorphism problem for graphs of

bounded tree width can be decided in logspace. In the light of isomorphism for

trees being hard for the complexity class logspace, this makes the ubiquitous

class of graphs of bounded tree width one of the few classes of graphs for which

the complexity of the isomorphism problem has been exactly determined.

The Closest Substring Problem is to decide, for given strings s_1, ..., s_k of length at most p and numbers m and d, whether there is a length-m string s and length-m substrings s'_i of s_i, such that s has a hamming distance of at most d from each s'_i. If we instead require the sum of all the hamming distances between s and each s'_i to be bounded by d, then it is called the Consensus Patterns Problem. We contribute to the parameterised complexity analysis of these classical NP-hard string problems by investigating the parameter (p - m), i.e., the length difference between input and solution strings. For most combinations of (p - m) and one of the classical parameters (m, p, k or d), we obtain fixed-parameter tractability. However, even for constant (p - m) and constant alphabet size, both problems remain NP-hard. While this follows from known results with respect to the Closest Substring Problem, we need a new reduction in the case of the Consensus Patterns Problem. As a by-product of this reduction, we obtain an exact exponential-time algorithm for both problems, which is based on an alphabet reduction.

Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing. The problem has multiple applications, e.g. in scheduling and stock-cutting, and has been studied extensively.

When the dimensions of objects are allowed to be exponential in the total input size, it is known that the problem cannot be approximated within a factor better than $3/2$, unless $\mathrm{P}=\mathrm{NP}$. However, there was no corresponding lower bound for polynomially bounded input data. In fact, Nadiradze and Wiese [SODA 2016] have recently proposed a $(1.4 + \epsilon)$ approximation algorithm for this variant, thus showing that strip packing with polynomially bounded data can be approximated better than when exponentially large values in the input data are allowed. Their result has subsequently been improved to a $(4/3 + \epsilon)$ approximation by two independent research groups [FSTTCS 2016, arXiv:1610.04430]. This raises a question whether strip packing with polynomially bounded input data admits a quasi-polynomial time approximation scheme, as is the case for related two-dimensional packing problems like maximum independent set of rectangles or two-dimensional knapsack.

In this paper we answer this question in negative by proving that it is NP-hard to approximate strip packing within a factor better than $12/11$, even when admitting only polynomially bounded input data. In particular, this shows that the strip packing problem admits no quasi-polynomial time approximation scheme, unless $\mathrm{NP} \subseteq \mathrm{DTIME}(2^{\mathrm{polylog}(n)})$.

We study two computational problems, parameterised by a fixed tree H. #HomsTo(H) is the problem of counting homomorphisms from an input graph G to H. #WHomsTo(H) is the problem of counting weighted homomorphisms to H, given an input graph G and a weight function for each vertex v of G. Even though H is a tree, these problems turn out to be sufficiently rich to capture all of the known approximation behaviour in #P. We give a complete trichotomy for #WHomsTo(H). If H is a star then #WHomsTo(H)$ is in FP. If H is not a star but it does not contain a certain induced subgraph J_3 then #WHomsTo(H) is equivalent under approximation-preserving (AP) reductions to #BIS, the problem of counting independent sets in a bipartite graph. This problem is complete for the class #RHPi_1 under AP-reductions. Finally, if H contains an induced J_3 then #WHomsTo(H)$ is equivalent under AP-reductions to #SAT, the problem of counting satisfying assignments to a CNF Boolean formula. Thus, #WHomsTo(H) is complete for #P under AP-reductions. The results are similar for #HomsTo(H) except that a rich structure emerges if H contains an induced J_3. We show that there are trees H for which #HomsTo(H) is #SAT-equivalent (disproving a plausible conjecture of Kelk). There is an interesting connection between these homomorphism-counting problems and the problem of approximating the partition function of the ferromagnetic Potts model. In particular, we show that for a family of graphs J_q, parameterised by a positive integer q, the problem #HomsTo(H) is AP-interreducible with the problem of approximating the partition function of the q-state Potts model. It was not previously known that the Potts model had a homomorphism-counting interpretation. We use this connection to obtain some additional upper bounds for the approximation complexity of #HomsTo(J_q).

We present and study a framework in which

one can present alternation-based lower bounds

on proof length in proof systems for quantified Boolean formulas.

A key notion in this framework is that of

proof system ensemble, which is

(essentially) a sequence of proof systems

where, for each, proof checking can be performed in

the polynomial hierarchy.

We introduce a proof system ensemble

called relaxing QU-res which is based on the

established proof system QU-resolution.

Our main results include an exponential separation of

the tree-like and general versions of relaxing QU-res,

and an exponential lower bound for relaxing QU-res;

these are analogs of

classical results in propositional proof complexity.