Search

We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph H to n-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for counting and detecting graph patterns, and also for obtaining natural polynomial families which are complete for algebraic complexity classes VBP, VP, and VNP. We discover that, in the monotone setting, the formula complexity, the ABP complexity, and the circuit complexity of such polynomial families are exactly characterized by the treedepth, the pathwidth, and the treewidth of the pattern graph respectively. Furthermore, we establish a single, unified framework, using our characterization, to collect several known results that were obtained independently via different methods. For instance, we attain superpolynomial separations between circuits, ABPs, and formulas in the monotone setting, where the polynomial families separating the classes all correspond to well-studied combinatorial problems. Moreover, our proofs rediscover fine-grained separations between these models for constant-degree polynomials., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 83:1-83:20

Lovász (1967) showed that two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph F, the number of homomorphisms from F to G equals the number of homomorphisms from F to H. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems. In this paper, we provide a unified algebraic framework for such results by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system. Following this framework, we obtain characterisations of homomorphism indistinguishability over several natural graph classes, namely trees of bounded degree, graphs of bounded pathwidth (answering a question of Dell et al. (2018)), and graphs of bounded treedepth., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 70:1-70:20

Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms.

Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this additional structure. On the negative side, we show with a novel approach that the space consumption of any (single-pass) dynamic programming algorithm on treedepth decompositions of depth d cannot be bounded by (2&minus, ϵ)d&middot, logO(1)n for Vertex Cover, (3&minus, logO(1)n for 3-Coloring and (3&minus, logO(1)n for Dominating Set for any ϵ&gt, 0. This formalizes the common intuition that dynamic programming algorithms on graph decompositions necessarily consume a lot of space and complements known results of the time-complexity of problems restricted to low-treewidth classes. We then show that treedepth lends itself to the design of branching algorithms. Specifically, we design two novel algorithms for Dominating Set on graphs of treedepth d: A pure branching algorithm that runs in time dO(d2)&middot, n and uses space O(d3logd+dlogn) and a hybrid of branching and dynamic programming that achieves a running time of O(3dlogd&middot, n) while using O(2ddlogd+dlogn) space.

We give asymptotically exact values for the treewidth ${tw}(G)$ of a random geometric graph $G\in{\mathcal G(n,r)}$ in $[0,\sqrt{n}]^2$. More precisely, let $r_c$ denote the threshold radius for the appearance of the giant component in ${\mathcal G(n,r)}$. We then show that for any constant $0 < r < r_c$, ${tw}(G)=\Theta(\frac{\log n}{\log \log n})$, and for $c$ being sufficiently large, and $r=r(n) \geq c$, ${tw}(G)=\Theta(r \sqrt{n})$. Our proofs show that for the corresponding values of $r$ the same asymptotic bounds also hold for the pathwidth and the treedepth of a random geometric graph.