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 , V P , 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. [ABSTRACT FROM AUTHOR]

The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth. In this paper, we show that the crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidth 3. The technique also shows that the crossing number and the rectilinear (a.k.a. straight-line) crossing number are identical for this graph class, and that we require only an O (n) × O (n) -grid to achieve such a drawing. Our techniques can further be extended to devise a 2-approximation for general graphs with pathwidth 3. One crucial ingredient here is that the crossing number of a graph with a separation pair can be lower-bounded using the crossing numbers of its cut-components, a result that may be interesting in its own right. Finally, we give a 4 w 3 -approximation of the crossing number for maximal graphs of pathwidth w . This is a constant approximation for bounded pathwidth. We complement this with an NP-hardness proof of the weighted crossing number already for pathwidth 3 graphs and bicliques K 3 , n . [ABSTRACT FROM AUTHOR]

In the I ntervalizing Coloured Graphs problem, one must decide for a given graph G = ( V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the number of colors is fixed, we give an exact algorithm that uses $2^{\mathcal {O}(n/\log n)}$ time. We also give an $\mathcal {O}^{\ast }(2^{n})$ algorithm for the case that the number of colors is not fixed. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract: For a given graph , the interval completion problem of G is to find an edge set F such that the supergraph of G is an interval graph and is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs. [Copyright &y& Elsevier]

Abstract: The d-dimensional hypercube, , is the graph on vertices, which correspond to the d-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate. The notion of Hamming graphs (denoted by ) generalizes the notion of hypercubes: The vertices correspond to the d-vectors where the components are from the set , and two of the vertices are adjacent if and only if the corresponding vectors differ in exactly one component. In this paper we show that the and the . [Copyright &y& Elsevier]

Abstract: Motivated by the desire to speed up dynamic programming algorithms for graphs of bounded treewidth, we initiate a study of the tradeoff between width and pathwidth of tree-decompositions. We therefore investigate the catwidth parameter which is the minimum width of any tree-decomposition of a graph G when the pathwidth of the tree T is 1. The catwidth parameter lies between the treewidth and the pathwidth of the graph, , and just as treewidth relates to chordal graphs and pathwidth relates to interval graphs, catwidth relates to what we call catval graphs. We introduce the notion of an extended asteroidal triple (XAT) and characterize catval graphs as the XAT-free chordal graphs. We provide alternative characterizations of these graphs, show that there are graph classes for which the various parameters differ by an arbitrary amount, and consider algorithms for computing catwidth. [Copyright &y& Elsevier]