We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given $\alpha \in (0,1)$, there exists a $c=c(\alpha)$ such that the following holds: there is a polynomial-time algorithm that, given a $D$-regular graph $G$ on $n$ vertices with $D\geq \alpha n$, determines whether $G$ contains a cycle on at least $n - c$ vertices. The problem becomes NP-complete if we drop either the density or the regularity condition. The algorithm combines tools from extremal graph theory and spectral partitioning as well as some further algorithmic ingredients.

We study the computational complexity of approximating the partition function of the ferromagnetic Ising model in the Lee-Yang circle of zeros given by |λ| = 1, where λ is the external field of the model. Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics, but have also been key in the recent deterministic approximation scheme for all |λ| ≠ 1 by Liu, Sinclair, and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle, and on the tantalising question of what happens in the circular arc around λ = 1, where on one hand the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability, and on the other hand the presence of Lee-Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point λ = 1; in fact, our techniques apply more generally to the whole unit circle |λ| = 1. We show #P-hardness for approximating the partition function on graphs of maximum degree Δ when b, the edge-interaction parameter, is in the interval and λ is a non-real on the unit circle. This result contrasts with known approximation algorithms when , and shows that the Lee-Yang circle of zeros is computationally intractable, even on bounded-degree graphs. Our inapproximability result is based on constructing rooted tree gadgets via a detailed understanding of the underlying dynamical systems, which are further parameterised by the degree of the root. The ferromagnetic Ising model has radically different behaviour than previously considered anti-ferromagnetic models, and showing our #P-hardness results in the whole Lee-Yang circle requires a new high-level strategy to construct the gadgets. To this end, we devise an elaborate inductive procedure to construct the required gadgets by taking into account the dependence between the degree of the root of the tree and the magnitude of the derivative at the fixpoint of the corresponding dynamical system. The full version (with all proofs) is available on arXiv at arxiv.org/abs/2006.14828.

We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the "yes" case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the "yes" case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would be strong negative evidence for the truth of the Unique Games Conjecture.

In this paper we show that for any graph H of order m and any graph G of order n and maximum degree $$\Delta $$ one can compute the number of subsets S of V(G) that induces a graph isomorphic to H in time $$O(c^m \cdot n )$$ for some constant $$c = c(\Delta ) >0$$ . This is essentially best possible (in the sense that there is no $$c^{o(m)}poly(n)$$ -time algorithm under the exponential time hypothesis).

In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polynomials $\mathcal C$ and show that if $p\in \cal C$ and there is a disk $D$ centered at zero in the complex plane such that $p(G)$ does not vanish on $D$ for all bounded degree graphs $G$, then for each $z$ in the interior of $D$ there exists a deterministic polynomial-time approximation algorithm for evaluating $p(G)$ at $z$. This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectures. Our work builds on a recent line of work initiated by Barvinok [ Found. Comput. Math., 16 (2016), pp. 329--342; Theory Comput., 11 (2015), pp. 339--355; Computing the Partition Function of a Polynomial on the Boolean Cube, 2015; Discrete Anal., 2 (2017), 34pp], which provides a new algorithmic approach besides the existing Markov chain Monte Carlo method and the correlation decay method for these types of problems.

In the traveling salesman problem (TSP), we are given a complete graph $K_n$ together with an integer weighting $w$ on the edges of $K_n$, and we are asked to find a Hamilton cycle of $K_n$ of minimum weight. Let $h(w)$ denote the average weight of a Hamilton cycle of $K_n$ for the weighting $w$. Vizing in 1973 asked whether there is a polynomial-time algorithm which always finds a Hamilton cycle of weight at most $h(w)$. He answered this question in the affirmative and subsequently Rublineckii, also in 1973, and others described several other TSP heuristics satisfying this property. In this paper, we prove a considerable generalization of Vizing's result: for each fixed $k$, we give an algorithm that decides whether, for any input edge weighting $w$ of $K_n$, there is a Hamilton cycle of $K_n$ of weight at most $h(w)-k$ (and constructs such a cycle if it exists). For $k$ fixed, the running time of the algorithm is polynomial in $n$, where the degree of the polynomial does not depend on $k$ (i.e., the generalized Vizing problem is fixed-parameter tractable with respect to the parameter $k$).

We consider the variation of Ramsey numbers introduced by Erdös and Pach [J. Graph Theory, 7 (1983), pp. 137--147], where instead of seeking complete or independent sets we only seek a $t$-homogeneous set, a vertex subset that induces a subgraph of minimum degree at least $t$ or the complement of such a graph. For any $\nu > 0$ and positive integer $k$, we show that any graph $G$ or its complement contains as an induced subgraph some graph $H$ on $\ell \ge k$ vertices with minimum degree at least $\frac12(\ell-1) + \nu$ provided that $G$ has at least $k^{\Omega(\nu^2)}$ vertices. We also show this to be the best possible in a sense. This may be viewed as correction to a result claimed in [P. Erdös and J. Pach, J. Graph Theory, 7 (1983), pp. 137--147]. For the above result, we permit $H$ to have order at least $k$. In the harder problem, where we insist that $H$ have exactly $k$ vertices, we do not obtain sharp results, although we show a way to translate results of one form of the problem to the other.

In this paper, we give the first polynomial-time algorithm for determining the edge expansion for a graph of fixed orientable genus. We show that for a multigraph $G$ with $m$ edges and orientable genus $g$, the edge expansion of $G$ can be determined in time $m^{O(g)}$. We show that the same is true for various other similar measures of edge connectivity.