Search

We show that every graph with pathwidth strictly less than a that contains no path on 2 b vertices as a subgraph has treedepth at most 10ab. The bound is best possible up to a constant factor. [ABSTRACT FROM AUTHOR]

The |$2$| -layer drawing model is a well-established paradigm to visualize bipartite graphs where vertices of the two parts lie on two horizontal lines and edges lie between these lines. Several beyond-planar graph classes have been studied under this model. Surprisingly, however, the fundamental class of |$k$| -planar graphs has been considered only for |$k=1$| in this context. We provide several contributions that address this gap in the literature. First, we show tight density bounds for the classes of |$2$| -layer |$k$| -planar graphs with |$k\in \{2,3,4,5\}$|⁠. Based on these results, we provide a Crossing Lemma for |$2$| -layer |$k$| -planar graphs, which then implies a general density bound for |$2$| -layer |$k$| -planar graphs. We prove this bound to be almost optimal with a corresponding lower bound construction. Finally, we study relationships between |$k$| -planarity and |$h$| -quasiplanarity in the |$2$| -layer model and show that |$2$| -layer |$k$| -planar graphs have pathwidth at most |$k+1$| while there are also |$2$| -layer |$k$| -planar graphs with pathwidth at least |$(k+3)/2$|⁠. [ABSTRACT FROM AUTHOR]

The circumference of a graph G with at least one cycle is the length of a longest cycle in G. A classic result of Birmel\'e [J. Graph Theory, 43 (2003), pp. 24--25] states that the treewidth of G is at most its circumference minus 1. In case G is 2-connected, this upper bound also holds for the pathwidth of G; in fact, even the treedepth of G is upper bounded by its circumference (Bria\'nski et al. [Treedepth vs circumference, Combinatorica, 43 (2023), pp. 659--664]). In this paper, we study whether similar bounds hold when replacing the circumference of G by its cocircumference, defined as the largest size of a bond in G, an inclusionwise minimal set of edges F such that G F has more components than G. In matroidal terms, the cocircumference of G is the circumference of the bond matroid of G. Our first result is the following "dual" version of Birmel'e's theorem: The treewidth of a graph G is at most its cocircumference. Our second and main result is an upper bound of 3k 2 on the pathwidth of a 2-connected graph G with cocircumference k. Contrary to circumference, no such bound holds for the treedepth of G. Our two upper bounds are best possible up to a constant factor. [ABSTRACT FROM AUTHOR]

Given two n-vertex graphs G1 and G2 of bounded treewidth, is there an n-vertex graph G of bounded treewidth having subgraphs isomorphic to G1 and G2? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if G1 is a binary tree and G2 is a ternary tree. We also provide an extensive study of cases where such "gluing"" is possible. In particular, we prove that if G1 has treewidth k and G2 has pathwidth \l, then there is an n-vertex graph of treewidth at most k + 3\l + 1 containing both G1 and G2 as subgraphs. [ABSTRACT FROM AUTHOR]

We prove that for every tree $T$ of radius $h$ , there is an integer $c$ such that every $T$ -minor-free graph is contained in $H\boxtimes K_c$ for some graph $H$ with pathwidth at most $2h-1$. This is a qualitative strengthening of the Excluded Tree Minor Theorem of Robertson and Seymour (GM I). We show that radius is the right parameter to consider in this setting, and $2h-1$ is the best possible bound. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) and an integer k, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set S ⊆ V of G such that for each v ∈ V , | N [ v ] ∩ S | is at most k. We investigate the parameterized complexity of the problem and obtain the following results for the MMDS problem. First, we show that the MMDS problem is NP-hard even on planar bipartite graphs. Next, we show that the MMDS problem is W[1]-hard for the parameter pathwidth (and thus, for treewidth) of the input graph. Then, for split graphs, we show that the MMDS problem is W[2]-hard for the parameter k. Further, we complement the pathwidth lower bound by an FPT algorithm when parameterized by the vertex cover number of input graph. In particular, we design a 2 O (v c) | V | O (1) time algorithm for the MMDS problem where vc is the vertex cover number of the input graph. Finally, we show that the running time lower bound based on ETH is tight for the vertex cover parameter. [ABSTRACT FROM AUTHOR]

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]

We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the path-width of G to within a ratio of O(t√log t). This is the first algorithm to achieve an f(t)-approximation for some function f. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th + 2 has treewidth at least t or contains a subdivision of a complete binary tree of height h + 1. The bound th + 2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c = 2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth Ω(kc) has treewidth at least k or contains a subdivision of a complete binary tree of height k. Our main technical algorithm takes a graph G and some (not necessarily optimal) tree decomposition of G of width t' in the input, and it computes in polynomial time an integer h, a certificate that G has pathwidth at least h, and a path decomposition of G of width at most (t' + 1)h + 1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height h. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth. [ABSTRACT FROM AUTHOR]

The clustered chromatic number of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$ -colourable with monochromatic components of size at most $c$. We determine the clustered chromatic number of any minor-closed class with bounded treedepth, and prove a best possible upper bound on the clustered chromatic number of any minor-closed class with bounded pathwidth. As a consequence, we determine the fractional clustered chromatic number of every minor-closed class. [ABSTRACT FROM AUTHOR]

We study the Length-Bounded Cut problem for special graph classes and from a parameterized complexity viewpoint. Here, we are given a graph G , two vertices s and t , and positive integers β and λ. The task is to find a set F of at most β edges such that each s - t -path of length at most λ in G contains some edge in F. Bazgan et al. [20] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph is a proper interval graph. We confirm this conjecture by providing a dynamic-programming-based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [15] for Length-Bounded Cut parameterized by pathwidth by showing W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms. [ABSTRACT FROM AUTHOR]

The localization game is a pursuit-evasion game analogous to Cops and Robbers, where the robber is invisible and the cops send distance probes in an attempt to identify the location of the robber. We present a novel graph parameter called the localization capture time, which measures how long the localization game lasts assuming optimal play. We conjecture that the localization capture time is linear in the order of the graph, and show that the conjecture holds for graph families such as trees and interval graphs. We study bounds on the localization capture time for trees and its monotone property on induced subgraphs of trees and more general graphs. We give upper bounds for the localization capture time on the incidence graphs of projective planes. We finish with new bounds on the localization number and localization capture time using treewidth. [ABSTRACT FROM AUTHOR]

The Maximum Covering Location Problem (MCLP) is a well-studied problem in the field of operations research. Given a network with positive or negative demands on the nodes, a positive integer k, the MCLP seeks to find k potential facility centers in the network such that the neighborhood coverage is maximized. We study the variant of MCLP where edges of the network are subject to random failures due to some disruptive events. One of the popular models capturing the unreliable nature of the facility location is the linear reliability ordering (LRO) model. In this model, with every edge e of the network, we associate its survival probability 0 ≤ pe ≤ 1, or equivalently, its failure probability 1 − pe. The failure correlation in LRO is the following: If an edge e fails then every edge e ′ with p e ′ ≤ p e surely fails. The task is to identify the positions of k facilities that maximize the expected coverage. We refer to this problem as Expected Coverage problem. We study the Expected Coverage problem from the parameterized complexity perspective and obtain the following results. 1. For the parameter pathwidth, we show that the Expected Coverage problem is W[1]-hard. We find this result a bit surprising, because the variant of the problem with non-negative demands is fixed-parameter tractable (FPT) parameterized by the treewidth of the input graph. 2. We complement the lower bound by the proof that Expected Coverage is FPT being parameterized by the treewidth and the maximum vertex degree. We give an algorithm that solves the problem in time 2 O (tw log Δ) n O (1) , where tw is the treewidth, Δ is the maximum vertex degree, and n the number of vertices of the input graph. In particular, since Δ ≤ n, it means the problem is solvable in time n O (tw) , that is, is in XP parameterized by treewidth. [ABSTRACT FROM AUTHOR]

We study the problem of embedding shortest-path metrics of weighted graphs into ℓp spaces. We introduce a new embedding technique based on low-depth decompositions of a graph via shortest paths. The notion of shortest path decomposition (SPD) depth is inductively defined: A (weighed) path graph has SPD depth 1. General graph has an SPD of depth k if it contains a shortest path whose deletion leads to a graph, each of whose components has SPD depth at most k - 1. In this paper we give an O(kmin{1/p,1/2})-distortion embedding for graphs of SPD depth at most k. This result is asymptotically tight for any fixed p > 1, while for p = 1 it is tight up to second order terms. As a corollary of this result, we show that graphs having pathwidth k embed into ℓp with distortion O(kmin{1/p,1/2}). For p = 1, this improves over the best previous bound of Lee and Sidiropoulos that was exponential in k; moreover, for other values of p it gives the first embeddings whose distortion is independent of the graph size n. Furthermore, we use the fact that planar graphs have SPD depth O(log n) to give a new proof that any planar graph embeds into ℓ1 with distortion O(√ log n). Our approach also gives new results for graphs with bounded treewidth, and for graphs excluding a fixed minor. [ABSTRACT FROM AUTHOR]

Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph G encodes the combinatorics of search trees on G, defined recursively by a root r together with search trees on each of the connected components of G − r. In particular, the skeleton of the graph associahedron is the rotation graph of those search trees. We investigate the diameter of graph associahedra as a function of some graph parameters. It is known that the diameter of the associahedra of paths of length n, the classical associahedra, is 2n - 6 for a large enough n. We give a tight bound of Θ(m) on the diameter of trivially perfect graph associahedra on m edges. We consider the maximum diameter of associahedra of graphs on n vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. Finally, we prove that the maximum diameter of associahedra of graphs of pathwidth two is Θ(n log n). [ABSTRACT FROM AUTHOR]

We show that a simple Markov chain, the Glauber dynamics, can efficiently sample independent sets almost uniformly at random in polynomial time for graphs in a certain class. The class is determined by boundedness of a new graph parameter called bipartite pathwidth. This result, which we prove for the more general hardcore distribution with fugacity λ, can be viewed as a strong generalization of Jerrum and Sinclair's work on approximately counting matchings, that is, independent sets in line graphs. The class of graphs with bounded bipartite pathwidth includes claw-free graphs, which generalize line graphs. We consider two further generalizations of claw-free graphs and prove that these classes have bounded bipartite pathwidth. We also show how to extend all our results to polynomially bounded vertex weights. [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.

The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be NP -complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph G. We show that the problem belongs to FPT when parameterised by the size of a minimum vertex cover for G, and is solvable in polynomial time whenever the treewidth or max leaf number of G is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set. [ABSTRACT FROM AUTHOR]

The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings such as intensional query evaluation on databases, we obtain Boolean circuits that satisfy some width bounds, e.g., they have bounded treewidth or pathwidth. In this work, we give a systematic picture of many circuit classes considered in knowledge compilation and show how they can be systematically connected to width measures, through upper and lower bounds. Our upper bounds show that bounded-treewidth circuits can be constructively converted to d-SDNNFs, in time linear in the circuit size and singly exponential in the treewidth; and that bounded-pathwidth circuits can similarly be converted to uOBDDs. We show matching lower bounds on the compilation of monotone DNF or CNF formulas to structured targets, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable): any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size in its treewidth, and the same holds for uOBDDs (resp., n-OBDDs) when considering pathwidth. Unlike most previous work, our bounds apply to any formula of this class, not just a well-chosen family. Hence, we show that pathwidth and treewidth respectively characterize the efficiency of compiling monotone DNFs to uOBDDs and d-SDNNFs with compilation being singly exponential in the corresponding width parameter. We also show that our lower bounds on CNFs extend to unstructured compilation targets, with an exponential lower bound in the treewidth (resp., pathwidth) when compiling monotone CNFs of constant arity and degree to DNNFs (resp., nFBDDs). [ABSTRACT FROM AUTHOR]

We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalizes a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class. [ABSTRACT FROM AUTHOR]

In this paper we study the hardness of the k -Center problem on inputs that model transportation networks. For the problem, a graph G = (V , E) with edge lengths and an integer k are given and a center set C ⊆ V needs to be chosen such that | C | ≤ k . The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the k -Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers k, the highway dimension h, and the pathwidth p. Moreover, under the exponential time hypothesis there is no f (k , p , h) · n o (p + k + h) time algorithm for any computable function f. Thus it is unlikely that the optimum solution to k -Center can be found efficiently, even when assuming that the input graph abides to all of the above models for transportation networks at once! Additionally we give a simple parameterized (1 + ε) -approximation algorithm for inputs of doubling dimension d with runtime (k k / ε O (k d)) · n O (1) . This generalizes a previous result, which considered inputs in D-dimensional L q metrics. [ABSTRACT FROM AUTHOR]

Similar to the satisfiability (SAT) problem, which can be seen to be the archetypical problem for NP, the quantified Boolean formula problem (QBF) is the archetypical problem for PSPACE. Recently, Atserias and Oliva (2014) showed that, unlike for SAT, many of the well-known decompositional parameters (such as treewidth and pathwidth) do not allow efficient algorithms for QBF. The main reason for this seems to be the lack of awareness of these parameters towards the dependencies between variables of a QBF formula. In this paper we extend the ordinary pathwidth to the QBF-setting by introducing prefix pathwidth, which takes into account the dependencies between variables in a QBF, and show that it leads to an efficient algorithm for QBF. We hope that our approach will help to initiate the study of novel tailor-made decompositional parameters for QBF and thereby help to lift the success of these decompositional parameters from SAT to QBF. [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]

We study the combinatorial FIFO Stack-Up problem. In the delivery industry, bins have to be moved from conveyor belts onto pallets. Given is a list Q of k sequences of labeled bins and a positive integer p. The goal is to palletize the bins by iteratively removing the first bin of one of the k sequences and putting it onto a pallet located at one of p stack-up places. Each of these pallets has to contain bins of only one label, bins of different labels have to be placed on different pallets. After all bins of one label have been removed from the given sequences, the corresponding stack-up place becomes available for a pallet of bins of another label. The FIFO Stack-Up problem asks whether such a processing is possible. The FIFO Stack-Up problem is known to be NP-complete even if the sequences of Q contain together at most c Q = 6 bins per pallet. This implies that the problem is also hard if all bins of every pallet are distributed to at most d Q = 6 sequences. In this paper we strengthen the hardness to the cases c Q = 5 and d Q = 3. We also show the hardness for the practical case where the number of sequences is smaller than the number of pallets, and we point out differences to related problems like 3D Bin Packing and Train Marshalling. [ABSTRACT FROM AUTHOR]

A connected path decomposition of a simple graph G is a path decomposition (X 1 , ... , X l) such that the subgraph of G induced by X 1 ∪ ⋯ ∪ X i is connected for each i ∈ { 1 , ... , l }. The connected pathwidth of G is then the minimum width over all connected path decompositions of G. We prove that for each fixed k , the connected pathwidth of any input graph can be computed in polynomial-time. This answers an open question raised by Fedor V. Fomin during the GRASTA 2017 workshop, since connected pathwidth is equivalent to the connected (monotone) node search game. [ABSTRACT FROM AUTHOR]