Search

Nearly a decade ago, Azrieli and Shmaya introduced the class of λ-Lipschitz games in which every player's payoff function is λ-Lipschitz with respect to the actions of the other players. They showed via the probabilistic method that n-player Lipschitz games with m strategies per player have pure ε-approximate Nash equilibria, for ε ≥ λ√8nlog(2mn). They left open, however, the question of how hard it is to find such an equilibrium. In this work, we develop an efficient reduction from more general games to Lipschitz games. We use this reduction to study both the query and computational complexity of algorithms finding λ-approximate pure Nash equilibria of λ-Lipschitz games and related classes. We show a query lower bound exponential in nλ/ε against randomized algorithms finding ε-approximate pure Nash equilibria of n-player, λ-Lipschitz games. We additionally present the first PPAD-completeness result for finding pure Nash equilibria in a class of finite, non-Bayesian games (we show this for λ-Lipschitz polymatrix games for suitable pairs of values ε and λ) in which both the proof of PPAD-hardness and the proof of containment in PPAD require novel approaches (in fact, our approach implies containment in PPAD for any class of Lipschitz games in which payoffs from mixed-strategy profiles can be deterministically computed), and present a definition of "randomized PPAD". We define and subsequently analyze the class of "Multi-Lipschitz games", a generalization of Lipschitz games involving player-specific Lipschitz parameters in which the value of interest appears to be the average of the individual Lipschitz parameters. We discuss a dichotomy of the deterministic query complexity of finding ε-approximate Nash equilibria of general games and, subsequently, a query lower bound for λ-Lipschitz games in which any non-trivial value of ε requires exponentially-many queries to achieve. We examine which parts of this extend to the concepts of approximate correlated and coarse correlated equilibria, and in the process generalize the edge-isoperimetric inequalities to generalizations of the hypercube. Finally, we improve the block update algorithm presented by Goldberg and Marmolejo to break the potential boundary of a 0.75-approximation factor, presenting a randomized algorithm achieving a 0.7368-approximate Nash equilibrium making polynomially-many profile queries of an n-player 1/n-1-Lipschitz game with an unbounded number of actions.

This thesis addresses computational questions arising in auctions with multiple goods available in multiple quantities, with a focus on establishing the tractability of auction mechanisms used in practice. It presents algorithms and hardness results for solving these auctions with the goal of maximising social welfare or revenue, and develops procedures to facilitate participating agents in expressing their preferences in the auction's bidding language. The 'strong-substitutes product-mix auction' was originally designed for the Bank of England by Paul Klemperer and continues to be run at least monthly. It introduces a novel bidding language, which allows agents to submit sealed-bid strong-substitutes preferences over an arbitrary number of goods available in multiple discrete units. We study this language geometrically and computationally, and establish connections to related bidding languages in the literature. In order to solve the strong-substitutes product-mix auction for social welfare, we develop the first efficient algorithms to find market-clearing prices and envy-free allocations of supply to participating bidders. The latter, in particular, requires solving a novel constrained matching problem. By contrast, we show that solving the auction for maximum revenue is APX-hard even in special cases, and present initial algorithms for this. Agents participating in this auction may have trouble expressing their preferences in the auction's bidding language when faced with a large number of goods or non-trivial demand. Instead, they may be able to answer queries about their value of a given bundle or their demand at given prices. We propose algorithms that learn a bidder's preferences, assuming access to a demand or valuation oracle. In a special case currently implemented by the Bank of England, we present a linear-time algorithm. We also show super-polynomial lower bounds on the query complexity in the general case. Our algorithms constitute the first approach for bidders to express non-trivial preferences in these languages, lowering the barrier for participation in the strong-substitutes product-mix auction. In the related 'arctic product-mix market', originally designed for the Icelandic government by Klemperer, buyers use a conceptually similar bidding language to express preferences across multiple divisible goods in conjunction with monetary budgets. In this setting we present a new coincidence of the solution concepts of competitive equilibrium and optimal revenue: market-clearing prices are unique, and these prices maximise not only social welfare but also revenue. We also provide an algorithm to identify these prices.

While the celebrated theory of NP-completeness has been very successful in explaining the intractability of many interesting problems, there still remain many natural and seemingly hard problems that are not known to be NP-hard. Several of these problems lie in the class of total NP search problems (TFNP), namely the class of NP search problems that always have a solution. Importantly, these problems cannot be NP-hard unless NP = co-NP. Notable examples of TFNP problems include FACTORING (given a natural number, compute its prime factorisation) and NASH (given a game, compute a mixed Nash equilibrium). In order to shed light on the complexity of these problems, researchers have attempted to classify them in various subclasses of TFNP such as PPAD, PPA, PPP, PLS, and CLS. A celebrated result in this line of research is the PPAD-completeness of NASH, yielding strong evidence that the problem is not polynomial-time solvable. In this thesis we provide new structural results for TFNP subclasses and show how they can be used to classify natural problems arising from application areas such as game theory and optimisation. In the first part of this work, we construct more powerful tools for proving membership in PPAD, as well as PPAD-hardness. We directly apply these tools to show that the Hairy Ball theorem from topology ("you can't comb a hairy ball flat without creating a cowlick"), as well as the equilibrium computation problem in First Price Auctions with subjective priors, are both PPAD-complete. In the second part of this thesis, we present our main result: the collapse CLS = PPAD ∩ PLS. We prove this surprising collapse by exhibiting the first non-artificial PPAD ∩ PLS-complete problem - a problem arising naturally from the famous gradient descent algorithm. Our result puts PPAD ∩ PLS on the map as a TFNP subclass that captures the complexity of natural problems. In the third and final part, we provide various structural results for the classes PPA-k (corresponding to arguments modulo k), including the first topological characterisations of these classes. As a direct application, we prove that NECKLACE-SPLITTING with k thieves - a notorious problem in combinatorics and fair division - lies in PPA-k under Turing reductions.

This thesis focuses on problems which themselves encode questions about circuits or algorithms, also called meta-computational problems. The thesis is centered on meta-computational problems like C-MCSP (minimum circuit size problem), C-Learnability and C-Satisfiability, for some circuit class C. We study mathematical questions pertaining to such problems, and their deep connections to the theory of lower bounds, which is a general theme that has attracted a lot of interest in recent years among complexity theorists. We first study non-uniform lower bounds for MCSP (and its variants) motivated by its importance for the theory of Hardness Magnification. Thisphenomenon reduces major complexity separations (such as NP is not in NC^1) to proving "barely" non-trivial lower bounds for natural problems like MCSP against weak circuit classes. In most interesting cases, we already have such required lower bounds, but for a different, seemingly easier problem. Firstly, we establish that instantiations of magnification for certain variants of MCSP provably refute the existence of natural proofs against P/poly, which indicates that the natural proofs barrier by Razborov-Rudich may not be relevant to this approach. This is done by establishing a connection from hardness magnification to hardness of efficiently learning polynomial-sized circuits. Next, we investigate the future prospects of proving new lower bounds using magnification. We identify a new source of difficulty called the locality barrier, when trying to adapt existing lower bound techniques to prove strong separations via magnification. We show that this barrier applies to many current instantiations of hardness magnification, that involve a wide range of restricted computational models. Next we consider learnability, and initiate a top-down study of hardness of learning circuit classes, i.e. we consider hardness of learning circuit classes more powerful than P/poly. Our goal is to understand the power and limitations of current complexity theoretic techniques in showing unconditional results for learning. We show unconditional hardness results for efficiently learning classes like BPE/poly, EXP/poly and PSPACE/poly on one hand, and on the other, show that it is implausible that one can extend these ideas to prove the NP-Hardness of learning classes like non-deterministic polynomial-sized circuits, i.e. NP/poly. Finally, we consider the algorithmic question of counting the number of satisfying assignments of an input AC^0[2]-circuit. We construct a deterministic #SAT-algorithm for AC^0[2] circuits of depth d and size 2^(O(n^(1/d))), which beats brute-force running time non-trivially. The algorithm is designed using the Razborov-Smolensky polynomial method, whose original motivation was to prove AC^0[2] lower bounds. We then show a lower bound for E^NP against AC^0[2]-circuits of size 2^(Ω(n^(1/d+1))), which was the best known lower bound against this class until very recently.

Given two graphs G and H, a function h that maps the vertices of G to vertices of H is a (graph) homomorphism if h preserves the edges of G, i.e., whenever two vertices u, v of G share an edge then h(u) and h(v) must share an edge in H. For different H, such homomorphisms represent different structures in G, thereby providing a framework that captures some of the most fundamental combinatorial problems studied in computer science and mathematics. One prominent example is the fact that homomorphisms from a graph G to a triangle (three vertices pairwise connected by edges) correspond to proper 3-colourings of G. Furthermore, counting homomorphisms has close ties to statistical physics and the computation of partition functions. The complexity of computing and approximating homomorphism counts has therefore drawn a lot of attention over the last four decades. One of the most intriguing open problems in this line of research is determining, for every graph H, the complexity of approximately counting homomorphisms to H. In this thesis, we investigate the complexity of several closely related problems. Our main objective is to establish complete complexity classifications for large classes of graph homomorphism counting problems. The focus is on counting homomorphisms that satisfy additional properties related to surjectivity. Apart from (unrestricted) homomorphisms, we mainly concentrate on: - (vertex-)surjective homomorphisms, - compactions (vertex- and non-loop-edge-surjective homomorphisms), - retractions (also known as pre-colouring extensions or one-or-all list homomorphisms). The main contributions of this thesis are as follows: • We give a complete complexity dichotomy for exactly counting surjective homomorphisms. This dichotomy is the same classification that also holds for exactly counting homomorphisms, list homomorphisms and retractions. • We give a complete complexity dichotomy for exactly counting compactions. Notably, this dichotomy is different from the dichotomy for surjective homomorphisms and shows that exactly counting compactions is actually the "hardest" of the aforementioned exact counting problems. • We present a collection of approximation-preserving reductions between different homomorphism counting problems. This includes reductions that establish that approximately counting retractions is at least as hard as approximately counting surjective homomorphisms and also at least as hard as approximately counting compactions. In these reductions we use a Monte Carlo sampling algorithm and this appears to be the first time such an approach has been used to obtain approximation-preserving reductions. • We formalise a framework that can be used to generate #BIS-easiness results for approximately counting homomorphisms and retractions. This framework is based on reduction techniques introduced by Dyer, Goldberg, Greenhill and Jerrum. • We give a complete complexity trichotomy for approximately counting retractions to all square-free graphs. As a consequence, we present separations between the problem of approximately counting homomorphisms and that of approximately counting retractions, as well as between the problem of approximately counting retractions and that of approximately counting list homomorphisms. • We present new #BIS-easiness results for approximately counting homomorphisms and thereby settle the complexity of this problem for a rich class of graphs for which it was previously unresolved. • We give a complete complexity dichotomy for counting homomorphisms modulo 2 to all K₄-minor-free graphs. This confirms a conjecture by Faben and Jerrum for this class of graphs. We use novel global hardness gadgets, which can be used to subsume all previously known classifications. We strengthen the hardness results by ruling out subexponential-time algorithms, assuming rETH.

Knowledge graphs (KGs) represent information in a simple, interlinked format and are used in a variety of applications. Besides the standard reasoning tasks such as query answering, there has been an increasing need for new types of analysis. One such fundamental analysis task is entity comparison, i.e., determining what two entities have in common and how they are different. The importance of such a task can be seen in various applications such as product comparisons, and explainable recommender systems. This thesis studies the problem of entity comparison over knowledge graphs and presents a novel framework that models comparisons via similarity and difference queries. It is the first declarative comparison framework for linked data that treats both similarities and differences as first-class citizens. We first define the syntax and semantics of various types of comparison queries, motivating each type with examples and establishing important relations between different query types. Next, we study the complexity of the two fundamental decision problems over queries, namely the existence and verification problems, for basic comparison queries and for most specific similarity queries (MSSQs). We consider two underlying fragments of SPARQL, with and without arithmetic comparisons, and we show how they affect the complexity of the above problems, and which types of data they suit most. We then study practical aspects of computing the MSSQ. In particular, we establish an important uniqueness result for MSSQs and propose an efficient approximation algorithm. We implement an algorithm for computing acyclic similarity queries and evaluate its performance on large-scale KGs; our empirical results demonstrate the practical feasibility of our algorithm.

A homomorphism from a graph G to a graph H is a function from V (G) to V (H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this thesis we study the complexity of various problems related to graph homomorphisms.

This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Qm in Qd. Specifically, we show that for m ≥ 2 fixed and d large there exists a subgraph G of Qd of bounded average degree such that G does not contain a copy of Qm but, for every G' such that G ⊊ G' ⊆ Qd, the graph G' contains a copy of Qm. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2(1-ε)k subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós. We also prove that there exists a constant c ∈ (0,1) such that the smallest such collection is of cardinality 2(1+o(1))ck for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Qm in Qd. That is, we determine the minimum number of edges in a spanning subgraph G of Qd such that the edges of E(Qd)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Qm. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A0 of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A0 percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r ≥ 2, every percolating set in Qd has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollobás and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset 𝒱(q,n) consisting of all subspaces of 𝔽qnordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in 𝒱(q,n) and a bound on the size of the largest antichain in a p-random subset of 𝒱(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (εi)∞i=1 tending to zero such that, for all i ≥ 1, every weak εi-regular partition of W has at least exp(εi-2/25log∗εi-2) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lovász and Szegedy. For positive integers p,q with p/q ❘≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → ℤp such that any two adjacent vertices are mapped to elements of ℤp at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 ≤ p/q < 4 and is PSPACE-complete for p/q ≥ 4.

The verification of real-time systems has gained much interest in the formal verification community during the past two decades. In this thesis, we investigate two real-time verification problems that benefit from the techniques normally used in untimed verification. The first part of this thesis is concerned with the monitoring of real-time specifications. We study the expressiveness of metric temporal logics over timed words, a problem that dates back to early 1990s. We show that the logic obtained by extending Metric Temporal Logic (MTL) with two families of new modalities is expressively complete for the Monadic First-Order Logic of Order and Metric (FO[<,+1]) in time-bounded settings. Furthermore, by allowing rational constants, expressive completeness also holds in the general (time-unbounded) setting. Finally, we incorporate several notions and techniques from LTL monitoring to obtain the first trace-length independent monitoring procedure for this logic. The second part of this thesis concerns a decision problem regarding UAVs: given a set of targets (each ascribed with a relative deadline) and flight times between each pair of targets, is there a way to coordinate a flock of k identical UAVs so that all targets are visited infinitely often and no target is ever left unvisited for a time longer than its relative deadline? We show that the problem is PSPACE-complete even in the single-UAV case, thereby corrects an erroneous claim from the literature. We then complement this result by proposing an efficient antichain-based approach where a delayed simulation is used to prune the state space. Experimental results clearly demonstrate the effectiveness of our approach.

In mathematical finance, the sensitivities of option prices to various market parameters, also known as the “Greeks”, reflect the exposure to different sources of risk. Computing these is essential to predict the impact of market moves on portfolios and to hedge them adequately. This is commonly done using Monte Carlo simulations. However, obtaining accurate estimates of the Greeks can be computationally costly. Multilevel Monte Carlo offers complexity improvements over standard Monte Carlo techniques. However the idea has never been used for the computation of Greeks. In this work we answer the following questions: can multilevel Monte Carlo be useful in this setting? If so, how can we construct efficient estimators? Finally, what computational savings can we expect from these new estimators? We develop multilevel Monte Carlo estimators for the Greeks of a range of options: European options with Lipschitz payoffs (e.g. call options), European options with discontinuous payoffs (e.g. digital options), Asian options, barrier options and lookback options. Special care is taken to construct efficient estimators for non-smooth and exotic payoffs. We obtain numerical results that demonstrate the computational benefits of our algorithms. We discuss the issues of convergence of pathwise sensitivities estimators. We show rigorously that the differentiation of common discretisation schemes for Ito processes does result in satisfactory estimators of the the exact solutions’ sensitivities. We also prove that pathwise sensitivities estimators can be used under some regularity conditions to compute the Greeks of options whose underlying asset’s price is modelled as an Ito process. We present several important results on the moments of the solutions of stochastic differential equations and their discretisations as well as the principles of the so-called “extreme path analysis”. We use these to develop a rigorous analysis of the complexity of the multilevel Monte Carlo Greeks estimators constructed earlier. The resulting complexity bounds appear to be sharp and prove that our multilevel algorithms are more efficient than those derived from standard Monte Carlo.

Query processing is a core task in probabilistic databases: Given a query and a database that encodes uncertainty in data by means of probability distributions, the problem is to compute possible query answers together with their respective probabilities of being correct. This thesis advances the state of the art in two aspects of query processing in probabilistic databases: complexity analysis and query evaluation techniques. A dichotomy is established for non-repeating, con- junctive relational algebra queries with negation that separates #P-hard queries from those with PTIME data complexity. A framework for computing proba- bilities of relational algebra queries is presented; the probability computation algorithm is based on decomposition methods and provides exact answers in the case of exhaustive decompositions, or anytime approximate answers with absolute or relative error guarantees in the case of partial decompositions. The framework is extended to queries with aggregation operators. An experimental evaluation of the proposed algorithms’ implementations within the SPROUT query engine complements the theoretical results. The SPROUT2 system uses this query engine to compute answers to queries on uncertain, tabular Web data.

Description Logics form a family of powerful ontology languages widely used by academics and industry experts to capture and intelligently manage knowledge about the world. A key advantage of Description Logics is their amenability to automated reasoning that enables the deduction of knowledge that has not been explicitly stated. However, in order to ensure decidability of automated reasoning algorithms, suitable restrictions are usually enforced on the shape of structures that are expressible using Description Logics. As a consequence, Description Logics fall short of expressive power when it comes to representing cyclic structures, which abound in life sciences and other disciplines. The objective of this thesis is to explore ontology languages that are better suited for the representation of structured objects. It is suggested that an alternative approach which relies on nonmonotonic existential rules can provide a promising candidate for modelling such domains. To this end, we have built a comprehensive theoretical and practical framework for the representation of structured entities along with a surface syntax designed to allow the creation of ontological descriptions in an intuitive way. Our formalism is based on nonmonotonic existential rules and exhibits a favourable balance between expressive power and computational as well as empirical tractability. In order to ensure decidability of reasoning, we introduce a number of acyclicity criteria that strictly generalise many of the existing ones. We also present a novel stratification condition that properly extends `classical' stratification and allows for capturing both definitional and conditional aspects of complex structures. The applicability of our formalism is supported by a prototypical implementation, which is based on an off-the-shelf answer set solver and is tested over a realistic knowledge base. Our experimental results demonstrate improvement of up to three orders of magnitude in comparison with previous evaluation efforts and also expose numerous modelling errors of a manually curated biochemical knowledge base. Overall, we believe that our work lays the practical and theoretical foundations of an ontology language that is well-suited for the representation of structured objects. From a modelling point of view, our approach could stimulate the adoption of a different and expressive reasoning paradigm for which robustly engineered mature reasoners are available; it could thus pave the way for the representation of a broader spectrum of knowledge. At the same time, our theoretical contributions reveal useful insights into logic-based knowledge representation and reasoning. Therefore, our results should be of value to ontology engineers and knowledge representation researchers alike.

Graph colourings and combinatorial games are two very widely studied topics in discrete mathematics. This thesis addresses the computational complexity of a range of problems falling within one or both of these subjects. Much of the thesis is concerned with the computational complexity of problems related to the combinatorial game (Free-)Flood-It, in which players aim to make a coloured graph monochromatic ("flood" the graph) with the minimum possible number of flooding operations; such problems are known to be computationally hard in many cases. We begin by proving some general structural results about the behaviour of the game, including a powerful characterisation of the number of moves required to flood a graph in terms of the number of moves required to flood its spanning trees; these structural results are then applied to prove tractability results about a number of flood-filling problems. We also consider the computational complexity of flood-filling problems when the game is played on a rectangular grid of fixed height (focussing in particular on 3xn and 2xn grids), answering an open question of Clifford, Jalsenius, Montanaro and Sach. The final chapter concerns the parameterised complexity of list problems on graphs of bounded treewidth. We prove structural results determining the list edge chromatic number and list total chromatic number of graphs with bounded treewidth and large maximum degree, which are special cases of the List (Edge) Colouring Conjecture and Total Colouring Conjecture respectively. Using these results, we show that the problem of determining either of these quantities is fixed parameter tractable, parameterised by the treewidth of the input graph. Finally, we analyse a list version of the Hamilton Path problem, and prove it to be W[1]-hard when parameterised by the pathwidth of the input graph. These results answer two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen.

The field of computational complexity theory--which chiefly aims to quantify the difficulty encountered when performing calculations--is, in the case of conventional computers, correctly practised and well understood (some important and fundamental open questions notwithstanding); however, such understanding is, we argue, lacking when unconventional paradigms are considered. As an illustration, we present here an analogue computer that performs the task of natural-number factorization using only polynomial time and space; the system's true, exponential complexity, which arises from requirements concerning precision, is overlooked by a traditional, `time-and-space' approach to complexity theory. Hence, we formulate the thesis that unconventional computers warrant unconventional complexity analysis; the crucial omission from traditional analysis, we suggest, is consideration of relevant resources, these being not only time and space, but also precision, energy, etc. In the presence of this multitude of resources, however, the task of comparing computers' efficiency (formerly a case merely of comparing time complexity) becomes difficult. We resolve this by introducing a notion of overall complexity, though this transpires to be incompatible with an unrestricted formulation of resource; accordingly, we define normality of resource, and stipulate that considered resources be normal, so as to rectify certain undesirable complexity behaviour. Our concept of overall complexity induces corresponding complexity classes, and we prove theorems concerning, for example, the inclusions therebetween. Our notions of resource, overall complexity, normality, etc. form a model-independent framework of computational complexity theory, which allows: insightful complexity analysis of unconventional computers; comparison of large, model-heterogeneous sets of computers, and correspondingly improved bounds upon the complexity of problems; assessment of novel, unconventional systems against existing, Turing-machine benchmarks; increased confidence in the difficulty of problems; etc. We apply notions of the framework to existing disputes in the literature, and consider in the context of the framework various fundamental questions concerning the nature of computation.

This thesis examines graph polynomials and particularly their complexity. We give short proofs of two results from Gessel and Sagan (1996) which present new evaluations of the Tutte polynomial concerning orientations. A theorem of Massey et al (1997) gives an expression concerning the average size of a forest in a graph. We generalise this result to any simplicial complex. We answer a question posed by Kleinschmidt and Onn (1995) by showing that the language of partitionable simplicial complexes is in NP. We prove the following result concerning the complexity of the Tutte polynomial: Theorem 1. For any fixed k, there exists a polynomial time algorithm A, which will input any graph G, with tree-width at most k, and rational numbers x and y, and evaluate the Tutte polynomial, T(G;x,y). The rank generating function S of a graphic 2-polymatroid was introduced by Oxley and Whittle (1993). It has many similarities to the Tutte polynomial and we prove the following results. Theorem 2. Evaluating S at a fixed point (u,v) is #P-hard unless uv=1 when there is a polynomial time algorithm. Theorem 3. For any fixed k, there exists a polynomial time algorithm A, which will input any graph G, with tree-width at most k, and rational numbers u and v, and evaluate S(G;u,v). We consider a class of graphs $S$, which are those graphs which are obtainable from a graph with no edges using the unsigned version of Reidemeister moves. We examine the relationship between this class and other similarly defined classes such as the delta-wye graphs. There remain many open questions such as whether S contains every graph. However we have an invariant of the moves, based on the Tutte polynomial, which allows us to determine from which graph with no edges, if any, a particular graph can be obtained. Finally we consider a new polynomial on weighted graphs which is motivated by the study of weight systems on chord diagrams. We give three states model and a recipe theorem. An unweighted version of this polynomial is shown to contain as specialisations, a wide range of graph invariants, such as the Tutte polynomial, the polymatroid polynomial of Oxley and Whittle (1993) and the symmetric function generalisation of the chromatic polynomial introduced by Stanley (1995). We close with a discussion of complexity issues proving hardness results for very restricted classes of graphs.

The final Chapter concerns a problem of partitioning graphs subject to certain restrictions. We prove that several subproblems are NP-complete.