12 results on '"Pathwidth"'
Search Results
2. 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
3. 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
4. Positive-Instance Driven Dynamic Programming for Graph Searching
- Author
-
Bannach, Max, Berndt, Sebastian, 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, Friggstad, Zachary, editor, Sack, Jörg-Rüdiger, editor, and Salavatipour, Mohammad R, editor
- Published
- 2019
- Full Text
- View/download PDF
5. 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
6. 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
7. 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
8. 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
9. Recent Advances in Positive-Instance Driven Graph Searching
- Author
-
Sebastian Berndt and Max Bannach
- Subjects
Computational Mathematics ,Numerical Analysis ,Computational Theory and Mathematics ,treewidth ,pathwidth ,treedepth ,graph searching ,positive-instance driven ,color coding ,Theoretical Computer Science - 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
10. Recent Advances in Positive-Instance Driven Graph Searching †.
- Author
-
Bannach, Max and Berndt, Sebastian
- Subjects
- *
DATA structures , *GRAPH algorithms , *DYNAMIC programming , *TREE graphs , *CHARTS, diagrams, etc. , *COLOR codes - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
11. Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
- Author
-
Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Li-Hsuan Chen
- Subjects
lcsh:T55.4-60.8 ,Vertex cover ,010103 numerical & computational mathematics ,0102 computer and information sciences ,01 natural sciences ,space lower bound ,lcsh:QA75.5-76.95 ,Theoretical Computer Science ,Pathwidth ,Dominating set ,treewidth ,lcsh:Industrial engineering. Management engineering ,ddc:510 ,0101 mathematics ,Mathematics ,Discrete mathematics ,dynamic programming ,Numerical Analysis ,branching algorithm ,treedepth ,Graph ,Running time ,Treewidth ,Dynamic programming ,Computational Mathematics ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Bounded function ,lcsh:Electronic computers. Computer science - Abstract
Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this additional structure. On the negative side, we show with a novel approach that the space consumption of any (single-pass) dynamic programming algorithm on treedepth decompositions of depth d cannot be bounded by (2&minus, ϵ)d·, logO(1)n for Vertex Cover, (3&minus, logO(1)n for 3-Coloring and (3&minus, logO(1)n for Dominating Set for any ϵ>, 0. This formalizes the common intuition that dynamic programming algorithms on graph decompositions necessarily consume a lot of space and complements known results of the time-complexity of problems restricted to low-treewidth classes. We then show that treedepth lends itself to the design of branching algorithms. Specifically, we design two novel algorithms for Dominating Set on graphs of treedepth d: A pure branching algorithm that runs in time dO(d2)·, n and uses space O(d3logd+dlogn) and a hybrid of branching and dynamic programming that achieves a running time of O(3dlogd·, n) while using O(2ddlogd+dlogn) space.
- Published
- 2018
12. On the treewidth and related parameters of random geometric graphs
- Author
-
Dieter Mitsche, Guillem Perarnau, Universitat Politècnica de Catalunya [Barcelona] (UPC), Christoph Dürr, Thomas Wilke, Laboratoire Jean Alexandre Dieudonné (JAD), Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), Applied Mathematics IV Department, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics, and Dürr, Christoph
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,General Mathematics ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,01 natural sciences ,Giant component ,Combinatorics ,010104 statistics & probability ,Pathwidth ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,treewidth ,0101 mathematics ,[MATH]Mathematics [math] ,Random geometric graph ,Mathematics ,Discrete mathematics ,000 Computer science, knowledge, general works ,Grafs, Teoria de ,pathwidth ,treedepth ,Radius ,Binary logarithm ,Treewidth ,Graph theory ,[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,010201 computation theory & mathematics ,Computer Science ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,Constant (mathematics) ,Random geometric graphs ,Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC] - Abstract
We give asymptotically exact values for the treewidth ${tw}(G)$ of a random geometric graph $G\in{\mathcal G(n,r)}$ in $[0,\sqrt{n}]^2$. More precisely, let $r_c$ denote the threshold radius for the appearance of the giant component in ${\mathcal G(n,r)}$. We then show that for any constant $0 < r < r_c$, ${tw}(G)=\Theta(\frac{\log n}{\log \log n})$, and for $c$ being sufficiently large, and $r=r(n) \geq c$, ${tw}(G)=\Theta(r \sqrt{n})$. Our proofs show that for the corresponding values of $r$ the same asymptotic bounds also hold for the pathwidth and the treedepth of a random geometric graph.
- Published
- 2012
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.