1,181 results on '"Pathwidth"'
Search Results
2. 2-Layer k-Planar Graphs Density, Crossing Lemma, Relationships And Pathwidth.
- Author
-
Angelini, Patrizio, Lozzo, Giordano Da, Förster, Henry, and Schneck, Thomas
- Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
3. PATHWIDTH VS COCIRCUMFERENCE.
- Author
-
BRIAŃSKI, MARCIN, JORET, GWENAËL JORET, and SEWERYN, MICHAŁT.
- Subjects
- *
MATROIDS , *GRAPH theory - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
4. THE TREEWIDTH AND PATHWIDTH OF GRAPH UNIONS.
- Author
-
ALECU, BOGDAN, LOZIN, VADIM V., QUIROZ, DANIEL A., RABINOVICH, ROMAN, RAZGON, IGOR, and ZAMARAEV, VIKTOR
- Subjects
- *
GLUE , *SENSES - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
5. The Excluded Tree Minor Theorem Revisited.
- Author
-
Dujmović, Vida, Hickingbotham, Robert, Joret, Gwenaël, Micek, Piotr, Morin, Pat, and Wood, David R.
- Subjects
MINORS ,TREES ,MATROIDS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
6. Parameterized Complexity of Minimum Membership Dominating Set.
- Author
-
Agrawal, Akanksha, Choudhary, Pratibha, Narayanaswamy, N. S., Nisha, K. K., and Ramamoorthi, Vijayaragunathan
- Subjects
- *
DOMINATING set , *BIPARTITE graphs , *PLANAR graphs , *NP-hard problems - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
7. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials.
- Author
-
Komarath, Balagopal, Pandey, Anurag, and Rahul, C. S.
- Subjects
- *
POLYNOMIALS , *ARITHMETIC , *CIRCUIT complexity , *HOMOMORPHISMS , *GRAPH algorithms - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
8. Approximating Pathwidth for Graphs of Small Treewidth.
- Author
-
GROENLAND, CARLA, JORET, GWENAËL, NADARA, WOJCIECH, and WALCZAK, BARTOSZ
- Subjects
APPROXIMATION algorithms ,TREE height ,POLYNOMIAL time algorithms ,GRAPH algorithms ,ALGORITHMS ,SUBDIVISION surfaces (Geometry) - Abstract
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 Ω(k
c ) 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]- Published
- 2023
- Full Text
- View/download PDF
9. Clustered colouring of graph classes with bounded treedepth or pathwidth.
- Author
-
Norin, Sergey, Scott, Alex, and Wood, David R.
- Subjects
RAMSEY numbers ,INTEGERS - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
10. 2-Layer k-Planar Graphs : Density, Crossing Lemma, Relationships, and Pathwidth
- Author
-
Angelini, Patrizio, Da Lozzo, Giordano, Förster, Henry, Schneck, Thomas, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Auber, David, editor, and Valtr, Pavel, editor
- Published
- 2020
- Full Text
- View/download PDF
11. Length-bounded cuts: Proper interval graphs and structural parameters.
- Author
-
Bentert, Matthias, Heeger, Klaus, and Knop, Dušan
- Subjects
- *
CHARTS, diagrams, etc. , *CUTTING stock problem , *INTEGERS , *LOGICAL prediction - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
12. The localization capture time of a graph.
- Author
-
Behague, Natalie C., Bonato, Anthony, Huggan, Melissa A., Marbach, Trent G., and Pittman, Brittany
- Subjects
- *
PROJECTIVE planes , *TREE graphs , *LINEAR orderings , *CHARTS, diagrams, etc. , *GENEALOGY , *SUBGRAPHS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
13. On the Parameterized Complexity of the Expected Coverage Problem.
- Author
-
Fomin, Fedor V. and Ramamoorthi, Vijayaragunathan
- Subjects
- *
LINEAR orderings , *OPERATIONS research , *INTEGERS , *PROBLEM solving - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
14. METRIC EMBEDDING VIA SHORTEST PATH DECOMPOSITIONS.
- Author
-
ABRAHAM, ITTAI, FILTSER, ARNOLD, GUPTA, ANUPAM, and NEIMAN, OFER
- Subjects
- *
PLANAR graphs , *WEIGHTED graphs , *EXPONENTIAL sums - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
15. Bounds on the Diameter of Graph Associahedra.
- Author
-
Cardinal, Jean, Pournin, Lionel, and Valencia-Pabon, Mario
- Subjects
COMBINATORICS ,SKELETON ,POLYTOPES ,ROTATIONAL motion ,TREES ,DIAMETER - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
16. Counting independent sets in graphs with bounded bipartite pathwidth.
- Author
-
Dyer, Martin, Greenhill, Catherine, and Müller, Haiko
- Subjects
INDEPENDENT sets ,POLYNOMIAL time algorithms ,BIPARTITE graphs ,MARKOV processes ,COUNTING ,FUGACITY - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
17. Recent Advances in Positive-Instance Driven Graph Searching
- Author
-
Max Bannach and Sebastian Berndt
- Subjects
treewidth ,pathwidth ,treedepth ,graph searching ,positive-instance driven ,color coding ,Industrial engineering. Management engineering ,T55.4-60.8 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2022
- Full Text
- View/download PDF
18. The Parameterised Complexity of Computing the Maximum Modularity of a Graph.
- Author
-
Meeks, Kitty and Skerman, Fiona
- Subjects
- *
ALGORITHMS , *POLYNOMIAL time algorithms , *QUADRATIC programming , *INTEGER programming - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
19. Connecting Knowledge Compilation Classes Width Parameters.
- Author
-
Amarilli, Antoine, Capelli, Florent, Monet, Mikaël, and Senellart, Pierre
- Subjects
- *
LOGIC circuits , *CIRCUIT complexity , *TIMING circuits , *BOOLEAN functions - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
20. MINOR-CLOSED GRAPH CLASSES WITH BOUNDED LAYERED PATHWIDTH.
- Author
-
DUJMOVIĆ, VIDA, EPPSTEIN, DAVID, JORET, GWENAËL, MORIN, PAT, and WOOD, DAVID R.
- Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
21. The Parameterized Hardness of the k-Center Problem in Transportation Networks.
- Author
-
Feldmann, Andreas Emil and Marx, Dániel
- Subjects
- *
PLANAR graphs , *COMPUTABLE functions , *HARDNESS , *APPROXIMATION algorithms - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
22. Using decomposition-parameters for QBF: Mind the prefix!
- Author
-
Eiben, Eduard, Ganian, Robert, and Ordyniak, Sebastian
- Subjects
- *
AWARENESS , *ALGORITHMS - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
23. Crossing Number for Graphs with Bounded Pathwidth.
- Author
-
Biedl, Therese, Chimani, Markus, Derka, Martin, and Mutzel, Petra
- Subjects
- *
GRAPH algorithms , *MAXIMAL functions - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
24. On the hardness of palletizing bins using FIFO queues.
- Author
-
Gurski, Frank, Rehs, Carolin, and Rethmann, Jochen
- Subjects
- *
FIRST in, first out (Queuing theory) , *CONVEYOR belts , *HARDNESS - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
25. Finding small-width connected path decompositions in polynomial time.
- Author
-
Dereniowski, Dariusz, Osula, Dorota, and Rzążewski, Paweł
- Subjects
- *
POLYNOMIAL time algorithms , *GRAPH connectivity , *OPEN-ended questions - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
26. Sur la largeur des décompositions JSJ compliquées
- Author
-
Huszár, Kristóf, Spreer, Jonathan, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), The University of Sydney, Chambers, Erin W., Gudmundsson, Joachim, ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), ANR-20-CE48-0007,AlgoKnot,Aspects algorithmiques et combinatoires de la théorie des nœuds(2020), ANR-18-CE40-0032,GrR,Reconfiguration de Graphes(2018), ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), and ANR-10-LABX-0059,CARMIN,Centers of Hosting and International Mathematical Encounters(2010)
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,F.2.2 ,G.2.2 ,generalized Heegaard splittings ,57Q15, 57N10, 05C75, 57M15 ,Theory of computation → Problems, reductions and completeness ,pathwidth ,triangulations ,Geometric Topology (math.GT) ,MSC: 57Q15, 57N10, 05C75, 57M15 ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,Mathematics of computing → Geometric topology ,computational 3-manifold topology ,Theory of computation → Fixed parameter tractability ,Mathematics - Geometric Topology ,ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory ,ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems ,fixed-parameter tractability ,JSJ decompositions ,[MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT] ,FOS: Mathematics ,treewidth ,Computer Science - Computational Geometry - Abstract
Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a "sufficiently complicated" JSJ decomposition of a 3-manifold enforces a "complicated structure" for all of its triangulations. More concretely, we show that, under certain conditions, the treewidth (resp. pathwidth) of the graph that captures the incidences between the pieces of the JSJ decomposition of an irreducible, closed, orientable 3-manifold M yields a linear lower bound on its treewidth tw (M) (resp. pathwidth pw(M)), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of M. We present several applications of this result. We give the first example of an infinite family of bounded-treewidth 3-manifolds with unbounded pathwidth. We construct Haken 3-manifolds with arbitrarily large treewidth - previously the existence of such 3-manifolds was only known in the non-Haken case. We also show that the problem of providing a constant-factor approximation for the treewidth (resp. pathwidth) of bounded-degree graphs efficiently reduces to computing a constant-factor approximation for the treewidth (resp. pathwidth) of 3-manifolds., LIPIcs, Vol. 258, 39th International Symposium on Computational Geometry (SoCG 2023), pages 42:1-42:18
- Published
- 2023
27. On width measures and topological problems on semi-complete digraphs.
- Author
-
Fomin, Fedor V. and Pilipczuk, Michał
- Subjects
- *
ALGORITHMS , *SYSTEMS on a chip , *COURTESY - Abstract
The topological theory for semi-complete digraphs, pioneered by Chudnovsky, Fradkin, Kim, Scott, and Seymour [10–12,28,43,39] , concentrates on the interplay between the most important width measures — cutwidth and pathwidth — and containment relations like topological/minor containment or immersion. We propose a new approach to this theory that is based on outdegree orderings and new families of obstacles for cutwidth and pathwidth. Using the new approach we are able to reprove the most important known results in a unified and simplified manner, as well as provide multiple improvements. Notably, we obtain a number of efficient approximation and fixed-parameter tractable algorithms for computing width measures of semi-complete digraphs, as well as fast fixed-parameter tractable algorithms for testing containment relations in the semi-complete setting. As a direct corollary of our work, we also derive explicit and essentially tight bounds on duality relations between width parameters and containment orderings in semi-complete digraphs. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
28. On Tradeoffs Between Width- and Fill-like Graph Parameters.
- Author
-
Dereniowski, Dariusz and Stański, Adam
- Subjects
- *
INTEGERS , *CONVEX bodies , *EDGES (Geometry) - Abstract
In this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1, ... , pw(G) + 1}, there exists an interval supergraph G′ of G such that for its clique number it holds ω (G ′) ≤ (1 + 2 t) (pw (G) + 1) and the number of its edges is bounded by |E(G′)| ≤ (t + 2)p(G). In other words, the pathwidth and the profile of a graph can be simultaneously minimized within the factors of 1 + 2 t (plus a small constant) and t + 2, respectively. Note that for a fixed t, both upper bounds provide constant factor approximations. On the negative side, we show an example that proves that, for some graphs, there is no solution in which both parameters are optimal. In case of finding a chordal supergraph, the two corresponding graph parameters that reflect its clique size and number of edges are the treewidth and fill-in. We obtain that the treewidth and the fill-in problems are also 'orthogonal' in the sense that for some graphs, a solution that minimizes one of those parameters cannot minimize the other. As a motivating example, we recall graph searching games which illustrates a need of simultaneous minimization of these pairs of graph parameters. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
29. Bounding the Search Number of Graph Products.
- Author
-
CLARKE, NANCY ELLEN, MESSINGER, MARGARET-ELLEN, and POWER, GRACE
- Subjects
- *
MANUFACTURED products - Abstract
In this paper, we provide results for the search number of the Cartesian product of graphs. We consider graphs on opposing ends of the spectrum: paths and cliques. Our main result determines the pathwidth of the product of cliques and provides a lower bound for the search number of the product of cliques. A consequence of this result is a bound for the search number of the product of arbitrary graphs G and H based on their respective clique numbers. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
30. XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
- Author
-
Bodlaender, Hans L., Groenland, Carla, Jacob, Hugo, Jaffke, Lars, Lima, Paloma T., Dell, Holger, Nederlof, Jesper, Sub Algorithms and Complexity, Sub Mathematical Modeling, and Algorithms and Complexity
- Subjects
bandwidth ,pathwidth ,linear mim-width ,XNLP ,W-hierarchy ,linear clique-width ,Software ,parameterized complexity - Abstract
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna [ToCT 2018], that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, (q-)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, and Bipartite Bandwidth.
- Published
- 2022
31. First Order Logic on Pathwidth Revisited Again
- Author
-
Lampis, Michael
- Subjects
FOS: Computer and information sciences ,FO logic ,Computer Science - Computational Complexity ,Computer Science - Logic in Computer Science ,Computer Science - Data Structures and Algorithms ,Theory of computation → Parameterized complexity and exact algorithms ,Data Structures and Algorithms (cs.DS) ,Pathwidth ,Computational Complexity (cs.CC) ,Algorithmic Meta-Theorems ,Logic in Computer Science (cs.LO) - Abstract
Courcelle’s celebrated theorem states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula. More devastatingly, this cannot be improved, under standard assumptions, even if we consider the much more restricted problem of deciding FO-expressible properties on trees. In this paper we revisit this well-studied topic and identify a natural special case where the dependence of Courcelle’s theorem can, in fact, be improved. Specifically, we show that all FO-expressible properties can be decided with an elementary dependence on the input formula, if the input graph has bounded pathwidth (rather than treewidth). This is a rare example of treewidth and pathwidth having different complexity behaviors. Our result is also in sharp contrast with MSO logic on graphs of bounded pathwidth, where it is known that the dependence has to be non-elementary, under standard assumptions. Our work builds upon, and generalizes, a corresponding meta-theorem by Gajarský and Hliněný for the more restricted class of graphs of bounded tree-depth., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 132:1-132:17
- Published
- 2022
32. Constrained Connectivity in Bounded X-Width Multi-Interface Networks
- Author
-
Alessandro Aloisio and Alfredo Navarra
- Subjects
multi-interface networks ,constrained connectivity ,energy optimization ,treewidth ,pathwidth ,carvingwidth ,Industrial engineering. Management engineering ,T55.4-60.8 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
As technology advances and the spreading of wireless devices grows, the establishment of interconnection networks is becoming crucial. Main activities that involve most of the people concern retrieving and sharing information from everywhere. In heterogeneous networks, devices can communicate by means of multiple interfaces. The choice of the most suitable interfaces to activate (switch-on) at each device results in the establishment of different connections. A connection is established when at its endpoints the devices activate at least one common interface. Each interface is assumed to consume a specific percentage of energy for its activation. This is referred to as the cost of an interface. Due to energy consumption issues, and the fact that most of the devices are battery powered, special effort must be devoted to suitable solutions that prolong the network lifetime. In this paper, we consider the so-called p-Coverage problem where each device can activate at most p of its available interfaces in order to establish all the desired connections of a given network of devices. As the problem has been shown to be NP -hard even for p = 2 and unitary costs of the interfaces, algorithmic design activities have focused in particular topologies where the problem is optimally solvable. Following this trend, we first show that the problem is polynomially solvable for graphs (modeling the underlying network) of bounded treewidth by means of the Courcelle’s theorem. Then, we provide two optimal polynomial time algorithms to solve the problem in two subclasses of graphs with bounded treewidth that are graphs of bounded pathwidth and graphs of bounded carvingwidth. The two solutions are obtained by means of dynamic programming techniques.
- Published
- 2020
- Full Text
- View/download PDF
33. The treewidth of line graphs.
- Author
-
Harvey, Daniel J. and Wood, David R.
- Subjects
- *
LINEAR statistical models , *INVARIANTS (Mathematics) , *ALGOL (Computer program language) , *GRAPH theory , *GEOMETRIC vertices - Abstract
The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs . We show that determining the treewidth of the line graph of a graph G is equivalent to determining the minimum vertex congestion of an embedding of G into a tree. Using this result, we prove sharp lower bounds in terms of both the minimum degree and average degree of G . These results are precise enough to exactly determine the treewidth of the line graph of a complete graph and other interesting examples. We also improve the best known upper bound on the treewidth of a line graph. Analogous results are proved for pathwidth. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
34. Linear ordering based MIP formulations for the vertex separation or pathwidth problem.
- Author
-
Mallach, Sven
- Abstract
Abstract We consider the task to compute the pathwidth of a graph which is known to be equivalent to solving the vertex separation problem. The latter is naturally modeled as a linear ordering problem with respect to the vertices of the graph. Present mixed-integer programs for the vertex separation problem express linear orders using either position or set assignment variables. However, as we show, the lower bound on the pathwidth obtained when solving their linear programming relaxations is zero for any directed graph. This is one reason for their limited utility in solving larger instances to optimality. We then present a new formulation that is based on conventional linear ordering variables and a slightly different perspective on the problem. Its relaxation provably delivers non-zero lower bounds for any graph whose pathwidth is non-zero. Further structural results for and extensions to this formulation are discussed. Finally, an experimental evaluation of three mixed-integer programs, each representing one of the different yet existing modeling approaches, displays their potentials and limitations when used to solve the problem to optimality in practice. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
35. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials
- Author
-
Balagopal Komarath, Anurag Pandey, and C. S. Rahul
- Subjects
Algebraic complexity ,General Computer Science ,Applied Mathematics ,Fixed-parameter algorithms and complexity ,Treewidth ,Graph homomorphisms ,Mathematics of computing → Graph algorithms ,Fine-grained complexity ,Algebraic circuits ,Homomorphism polynomials ,Pathwidth ,Computer Science::Computational Complexity ,Monotone complexity ,Computer Science Applications ,Treedepth ,Algebraic branching programs ,Algebraic formulas ,Theory of computation → Parameterized complexity and exact algorithms ,Graph algorithms ,Theory of computation → Algebraic complexity theory ,Theory of computation → Computational complexity and cryptography ,Theory of computation → Circuit complexity - Abstract
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
- Published
- 2022
- Full Text
- View/download PDF
36. Homomorphism Tensors and Linear Equations
- Author
-
Grohe, Martin, Rattan, Gaurav, and Seppelt, Tim
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,pathwidth ,treedepth ,Mathematics of computing → Discrete mathematics ,G.2.1 ,G.2.2 ,homomorphisms ,labelled graphs ,Sherali-Adams relaxation ,FOS: Mathematics ,treewidth ,Weisfeiler-Leman ,Mathematics - Combinatorics ,Wiegmann-Specht Theorem ,Combinatorics (math.CO) ,linear equations ,Computer Science - Discrete Mathematics ,05C60, 05C76, 05C05, 05C38, 05C50, 05E10, 20M32 - Abstract
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
- Published
- 2022
- Full Text
- View/download PDF
37. Parameterized Complexity of a Parallel Machine Scheduling Problem
- Author
-
Mallem, Maher, Hanen, Claire, Munier-Kordon, Alix, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université Paris Nanterre - Département de Mathématiques et Informatique, Université Paris Nanterre (UPN), and Architecture et Logiciels pour Systèmes Embarqués sur Puce (ALSOC)
- Subjects
parallel processors ,chains ,pathwidth ,Theory of computation → Problems, reductions and completeness ,precedence delays ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,scheduling ,parameterized complexity - Abstract
In this paper we consider the parameterized complexity of two versions of a parallel machine scheduling problem with precedence delays, unit processing times and time windows. In the first version - with exact delays - we assume that the delay between two jobs must be exactly respected, whereas in the second version - with minimum delays - the delay between two jobs is a lower bound on the time between them. Two parameters are considered for this analysis: the pathwidth of the interval graph induced by the time windows and the maximum precedence delay value. We prove that our problems are para-NP-complete with respect to any of the two parameters and fixed-parameter tractable parameterized by the pair of parameters., LIPIcs, Vol. 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), pages 21:1-21:21
- Published
- 2022
- Full Text
- View/download PDF
38. The treewidth of proofs.
- Author
-
Müller, Moritz and Szeider, Stefan
- Subjects
- *
DIRECTED graphs , *PROOF theory , *PATHS & cycles in graph theory , *AXIOMS , *TOPOLOGICAL spaces , *MATHEMATICAL bounds - Abstract
So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. Ordered pathwidth is roughly the same as proof space and the ordered treewidth of a proof is meant to serve as a measure of how far it is from being treelike. Length-space lower bounds for k -DNF refutations are generalized to arbitrary infinity axioms and strengthened in that the space measure is relaxed to ordered treewidth. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
39. ON TREEWIDTH AND RELATED PARAMETERS OF RANDOM GEOMETRIC GRAPHS.
- Author
-
MITSCHE, DIETER and PERARNAU, GUILLEM
- Subjects
- *
MATHEMATICAL proofs , *TREE graphs , *GRAPH theory , *TREE codes (Coding theory) , *GEOMETRY - Abstract
We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G ∈ G(n, r) in [0, √n]². More precisely, let rc denote the threshold radius for the appearance of the giant component in G(n, r). We then show that for any constant 0 < r < rc, tw(G) = Θ(log n/log log n), and for c being sufficiently large, and r = r(n) ≥ c, tw(G) = Θ(r√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. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
40. STRUCTURE OF GRAPHS WITH LOCALLY RESTRICTED CROSSINGS.
- Author
-
DUJMOVIĆ, VIDA, EPPSTEIN, DAVID, and WOOD, DAVID R.
- Subjects
- *
PLANAR graphs , *CROSSING numbers (Graph theory) , *GRAPH theory , *EMBEDDINGS (Mathematics) , *LOGARITHMIC functions - Abstract
We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth O(√(g + 1)(k + 1)n) and layered treewidth O((g + 1)k) and t hat these bounds are tight up to a constant factor. In the special case of g = 0, so-called k-planar graphs, the treewidth bound is O(√((k + 1)n), which is tight and improves upon a known O( (k + 1)3/4n1/2) bound. Analogous results are proved for map graphs defined with respect to any surface. Finally, we show that for g < m, every m-edge graph can be embedded on a surface of genus g with O((m/(g + 1)) log² g) crossings per edge, which is tight to a polylogarithmic factor. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
41. The firefighter problem: Further steps in understanding its complexity.
- Author
-
Chlebíková, Janka and Chopin, Morgan
- Subjects
- *
FIRE fighters , *FIREFIGHTING , *FIRE prevention , *FIRE extinguishers , *COMMAND & control at fires - Abstract
We consider the complexity of the firefighter problem where a budget of b ≥ 1 firefighters are available at each time step. This problem is known to be NP-complete even on trees of degree at most three and b = 1 [14] and on trees of bounded degree ( b + 3 ) for any fixed b ≥ 2 [4] . In this paper we provide further insight into the complexity landscape of the problem by showing a complexity dichotomy result with respect to the parameters pathwidth and maximum degree of the input graph. More precisely, first, we prove that the problem is NP-complete even on trees of pathwidth at most three for any b ≥ 1 . Then we show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter “pathwidth” and “maximum degree” of the input graph. Finally, we show that the problem remains NP-complete on very dense graphs, namely co-bipartite graphs, but is fixed-parameter tractable with respect to the parameter “cluster vertex deletion”. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
42. Exclusive Graph Searching.
- Author
-
Blin, Lélia, Burman, Janna, and Nisse, Nicolas
- Subjects
- *
GRAPH theory , *SEARCH algorithms , *MONOTONIC functions , *POLYNOMIAL time algorithms , *INTEGERS - Abstract
This paper tackles the well known graph searching problem, where a team of searchers aims at capturing an intruder in a network, modeled as a graph. This problem has been mainly studied for its relationship with the pathwidth of graphs. All variants of this problem assume that any node can be simultaneously occupied by several searchers. This assumption may be unrealistic, e.g., in the case of searchers modeling physical searchers, or may require each individual node to provide additional resources, e.g., in the case of searchers modeling software agents. We thus introduce and investigate exclusive graph searching, in which no two or more searchers can occupy the same node at the same time. As for the classical variants of graph searching, we study the minimum number of searchers required to capture the intruder. This number is called the exclusive search number of the considered graph. Exclusive graph searching appears to be considerably more complex than classical graph searching, for at least two reasons: (1) it does not satisfy the monotonicity property, and (2) it is not closed under minor. Moreover, we observe that the exclusive search number of a tree may differ exponentially from the values of classical search numbers (e.g., pathwidth). Nevertheless, we design a polynomial-time algorithm which, given any n-node tree T, computes the exclusive search number of T in time $$O(n^3)$$ . Moreover, for any integer k, we provide a characterization of the trees T with exclusive search number at most k. Finally, we prove that the ratio between the exclusive search number and the pathwidth of a graph is bounded by its maximum degree. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
43. Exclusive graph searching vs. pathwidth.
- Author
-
Markou, Euripides, Nisse, Nicolas, and Pérennes, Stéphane
- Subjects
- *
GRAPH theory , *MONOTONE operators , *COMPUTATIONAL complexity , *POLYNOMIAL time algorithms , *COMPLETENESS theorem - Abstract
In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. In this paper, we study the complexity of the Exclusive Graph Searching variant. We show that the problem is NP-hard in planar graphs and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
44. Treewidth and Pathwidth parameterized by the vertex cover number.
- Author
-
Chapelle, Mathieu, Liedloff, Mathieu, Todinca, Ioan, and Villanger, Yngve
- Subjects
- *
PARAMETERIZATION , *KERNEL (Mathematics) , *TREE graphs , *POLYNOMIALS , *GEOMETRIC vertices - Abstract
After the number of vertices, Vertex Cover Number is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover Number . Here we consider the treewidth and pathwidth problems parameterized by k , the size of a minimum vertex cover of the input graph. We show that the pathwidth and treewidth can be computed in O ∗ ( 3 k ) time. This complements recent polynomial kernel results for treewidth and pathwidth parameterized by the Vertex Cover Number . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
45. Parametrised Complexity of Satisfiability in Temporal Logic.
- Author
-
LÜCK, MARTIN, MEIER, ARNE, and SCHINDLER, IRENA
- Subjects
LOGIC ,LATTICE theory ,BOOLEAN functions ,PROPOSITION (Logic) ,MATHEMATICAL formulas - Abstract
We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and corresponding notions of treewidth and pathwidth are introduced. As an application for such structures, we present a classification in terms of parametrised complexity of the satisfiability problem, where we make use of Courcelle's famous theorem for recognition of certain classes of structures. Our classification shows a dichotomy between W[1]-hard and fixed-parameter tractable operator fragments almost independently of the chosen graph representation. The only fragments that are proven to be fixed-parameter tractable (FPT) are those that are restricted to the X operator. By investigating Boolean operator fragments in the sense of Post's lattice, we achieve the same complexity as in the unrestricted case if the set of available Boolean functions can express the function "negation of the implication." Conversely, we show containment in FPT for almost all other clones. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
46. On the Number of Labeled Graphs of Bounded Treewidth.
- Author
-
Baste, Julien, Noy, Marc, and Sau, Ignasi
- Abstract
Let be the number of labeled graphs on
n vertices and treewidth at mostk (equivalently, the number of labeled partialk -trees). We show that ]> ]> k > 1 ]> ]> ]> c > 0 ]> ]> ]> ( log k ) n ]> . The upper bound is a direct consequence of the well-known formula for the number of labeledk -trees, while the lower bound is obtained from an explicit construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at mostk . [ABSTRACT FROM AUTHOR]- Published
- 2017
- Full Text
- View/download PDF
47. THE MIXED CHINESE POSTMAN PROBLEM PARAMETERIZED BY PATHWIDTH AND TREEDEPTH.
- Author
-
GUTIN, GREGORY, JONES, MARK, and WAHLSTRÖM, MAGNUS
- Subjects
- *
GRAPH theory , *PARAMETERIZATION , *ROUTE inspection problem , *EDGES (Geometry) , *COMPUTATIONAL complexity - Abstract
In the mixed Chinese postman problem (MCPP), given a weighted mixed graph G (it may have both edges and arcs), our aim is to find a closed walk of minimum weight traversing each edge and arc at least once. The MCPP parameterized by the number of edges in G or the number of arcs in G is fixed-parameter tractable as proved by van Bevern et al. in 2014 and Gutin, Jones, and Sheng in 2014, respectively. Solving an open question of van Bevern et al., we show that somewhat unexpectedly the MCPP parameterized by the (undirected) treewidth of G is W[1]-hard. In fact, we prove that even the unweighted MCPP parameterized by the pathwidth of G is W[1]-hard. On the positive side, we show that MCPP parameterized by treedepth is fixed-parameter tractable (even with arbitrary integer weights). We are unaware of any widely studied graph parameters between pathwidth and treedepth and so our results provide a close characterization of the complexity of MCPP. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
48. Connected Search for a Lazy Robber
- Author
-
Isolde Adler, Christophe Paul, Dimitrios M. Thilikos, School of Computing [Leeds], University of Leeds, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Arkadev Chattopadhyay, Paul Gastin, ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), and ANR-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017)
- Subjects
Class (set theory) ,Computer Science::Computer Science and Game Theory ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Obstructions ,0102 computer and information sciences ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,01 natural sciences ,Combinatorics ,Set (abstract data type) ,Computer Science::Robotics ,Pathwidth ,Computer Science::Discrete Mathematics ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,Discrete Mathematics and Combinatorics ,Tree-decomposition ,0101 mathematics ,ComputingMilieux_MISCELLANEOUS ,Mathematics ,Graph searching ,000 Computer science, knowledge, general works ,010102 general mathematics ,Tree (graph theory) ,Treewidth ,Search game ,Monotone polygon ,010201 computation theory & mathematics ,Bounded function ,Computer Science ,Geometry and Topology - Abstract
International audience; The node search game against a lazy (or, respectively, agile) invisible robber has been introduced as a search-game analogue of the treewidth parameter (and, respectively, pathwidth). In the \emph{connected} variants of the above two games, we additionally demand that, at each moment of the search, the \emph{clean} territories are {\sl connected}. The connected search game against an agile and invisible robberhas been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of {\sl connected pathwidth}. It is known that \emph{the price of connectivtiy} to search for an agile robber is bounded by $2$, that is the connected pathwidth of a graph is at most twice (plus some constant) its pathwidth.In this paper, we investigate the study of the connected search game against a {\sl lazy} robber. A lazy robber moves only when the searchers' strategy threatens the location that he currently occupies. We introduce two alternative graph-theoretical formulations of this game, one in terms of connected tree decompositions, and one in terms of (connected) layouts, leading to the graph parameter of {\sl connected treewidth}. We observe that connected treewidth parameter is closed under contractions and prove that for every $k\geq 2$, the set of contraction obstructions of the class of graphs with connected treewidth at most $k$ is infinite.Our main result is a complete characterisation of the obstruction set for $k=2$. One may observe that, so far, only a few complete obstruction sets are explicity known for contraction closed graph classes.We finally show that, in contrast to the agile robber game, the price of connectivity is unbounded.
- Published
- 2021
49. Posets with Cover Graph of Pathwidth two have Bounded Dimension.
- Author
-
Biró, Csaba, Keller, Mitchel T., and Young, Stephen J.
- Abstract
Joret, Micek, Milans, Trotter, Walczak, and Wang recently asked if there exists a constant d such that if P is a poset with cover graph of P of pathwidth at most 2, then dim(P) ≤ d. We answer this question in the affirmative by showing that d = 17 is sufficient. We also show that if P is a poset containing the standard example S
5 as a subposet, then the cover graph of P has treewidth at least 3. [ABSTRACT FROM AUTHOR]- Published
- 2016
- Full Text
- View/download PDF
50. Computing Directed Pathwidth in $$O(1.89^{n})$$ Time.
- Author
-
Kitsunai, Kenta, Kobayashi, Yasuaki, Komuro, Keita, Tamaki, Hisao, and Tano, Toshihiro
- Subjects
- *
ALGORITHMS , *DIRECTED graphs , *GEOMETRIC vertices , *UNDIRECTED graphs , *GRAPH theory - Abstract
We give an algorithm for computing the directed pathwidth of a digraph with n vertices in $$O(1.89^{n})$$ time. This is the first algorithm with running time better than the straightforward $$O^{*}(2^n)$$ . As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in $$O(1.9657^n)$$ time. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.