Dariusz Dereniowski · HAL (Le Centre pour la Communication Scientifique Directe) · 2010
It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot\pw(G)+1$, where $\pw(G)$ is the pathwidth of $G$. The method is constructive, i.e. it yields an efficient algorithm that for a given path decomposition of width $k$ computes a connected path decomposition of width at most $2k+1$. The running time of the algorithm is $O(dk^2)$, where $d$ is the number of `bags' in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality $\csn(G)\leq 2\sn(G)+3$, where $\csn(G)$ and $\sn(G)$ are the connected search number and the search number of $G$. Moreover, the algorithm presented in this work can be used to convert a given search strategy using $k$ searchers into a (monotone) connected one using $2k+3$ searchers and starting at an arbitrary homebase.
Cited by 0Open access
Dariusz Dereniowskiy · 2016
It is proven that the connected pathwidth of any graphG is at most 2pw(G)+1, where pw(G) is the pathwidth of G. The method is constructive, i.e. it yields an efficient algorithm that for a given path decomposition of width k computes a connected path decomposition of width at most 2k + 1. The running time of the algorithm is O(dk2), where d is the number of `bags ' in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality cs(G) 2s(G) + 3, where cs(G) and s(G) are the connected search number and the search number of G, respectively. Moreover, the algorithm presented in this work can be used to convert a given search strategy using k searchers into a (monotone) connected one using 2k + 3 searchers and starting at an arbitrary homebase.
Cited by 0
Babak Miraftab, MorinPat, Yelena Yuditsky · ArXiv.org · 2026
We prove two results relating the basis number of a graph $G$ to path decompositions of $G$. Our first result shows that the basis number of a graph is at most four times its pathwidth. Our second result shows that, if a graph $G$ has a path decomposition with adhesions of size at most $k$ in which the graph induced by each bag has basis number at most $b$, then $G$ has basis number at most $b+O(k\log^2 k)$. The first result, combined with recent work of Geniet and Giocanti shows that the basis number of a graph is bounded by a polynomial function of its treewidth. The second result (also combined with the work of Geniet and Giocanti) shows that every $K_t$-minor-free graph has a basis number bounded by a polynomial function of $t$.
Cited by 0Open access
Hajebi, Sepehr · arXiv (Cornell University) · 2025
Dallard, Milanič, and Štorgel conjectured that for a hereditary graph class $\mathcal{G}$, if there is some function $f:\mathbb{N}\to\mathbb{N}$ such that every graph $G\in \mathcal{G}$ with clique number $ω(G)$ has treewidth at most $f(ω(G))$, then there is a polynomial function $f$ with the same property. Chudnovsky and Trotignon refuted this conjecture in a strong sense, showing that neither polynomial nor any prescribed growth can be guaranteed in general. Here we prove that, in stark contrast, the analog of the Dallard-Milanič-Štorgel conjecture for pathwidth is true: For every hereditary graph class $\mathcal{G}$, if the pathwidth of every graph in $\mathcal{G}$ is bounded by some function of its clique number, then the pathwidth of every graph in $\mathcal{G}$ is bounded by a polynomial function of its clique number.
Cited by 0Open access
Rodney G. Downey, Catherine Mccartin · 2015
The role of graph width metrics, such as treewidth, pathwidth, and cliquewidth, is now seen as central in both algorithm design and the delineation of what is algorithmically possible. In this article we introduce a new, related, parameter for graphs, persistence. A path decomposition of width k, in which every vertex of the underlying graph belongs to at most l nodes of the path, has pathwidth k and persistence l, and a graph that admits such a decomposition has bounded persistence pathwidth. We believe that this natural notion truly cap-tures the intuition behind the notion of pathwidth. We present some basic results regarding the gen-eral recognition of graphs having bounded persistence path decompositions.
Cited by 0
Hajebi, Sepehr · ArXiv.org · 2025
Dallard, Milanič, and Štorgel conjectured that for a hereditary graph class $\mathcal{G}$, if there is some function $f:\mathbb{N}\to\mathbb{N}$ such that every graph $G\in \mathcal{G}$ with clique number $ω(G)$ has treewidth at most $f(ω(G))$, then there is a polynomial function $f$ with the same property. Chudnovsky and Trotignon refuted this conjecture in a strong sense, showing that neither polynomial nor any prescribed growth can be guaranteed in general. Here we prove that, in stark contrast, the analog of the Dallard-Milanič-Štorgel conjecture for pathwidth is true: For every hereditary graph class $\mathcal{G}$, if the pathwidth of every graph in $\mathcal{G}$ is bounded by some function of its clique number, then the pathwidth of every graph in $\mathcal{G}$ is bounded by a polynomial function of its clique number.
Cited by 0Open access
Hiroshi Nagamochi · Lecture notes in computer science · 2012
Cited by 1
Frank Gurski, Jochen Rethmann, Egon Wanke · Lecture notes in computer science · 2015
Cited by 3
Babak Miraftab, MorinPat, Yelena Yuditsky · arXiv (Cornell University) · 2026
We prove two results relating the basis number of a graph $G$ to path decompositions of $G$. Our first result shows that the basis number of a graph is at most four times its pathwidth. Our second result shows that, if a graph $G$ has a path decomposition with adhesions of size at most $k$ in which the graph induced by each bag has basis number at most $b$, then $G$ has basis number at most $b+O(k\log^2 k)$. The first result, combined with recent work of Geniet and Giocanti shows that the basis number of a graph is bounded by a polynomial function of its treewidth. The second result (also combined with the work of Geniet and Giocanti) shows that every $K_t$-minor-free graph has a basis number bounded by a polynomial function of $t$.
Cited by 0Open access
Rodney G. Downey, Catherine Mccartin · 2008
The role of graph width metrics, such as treewidth, pathwidth, and cliquewidth, is now seen as central in both algorithm design and the delineation of what is algorithmically possible. In this article we introduce a new, related, parameter for graphs, persistence. A path decomposition of width k, in which every vertex of the underlying graph belongs to at most l nodes of the path, has pathwidth k and persistence l, and a graph that admits such a decomposition has bounded persistence pathwidth. We believe that this natural notion truly captures the intuition behind the notion of pathwidth. We present some basic results regarding the general recognition of graphs having bounded persistence path decompositions.
Cited by 0
Nikhil Bansal, Dor Katzelnick, Roy Schwartz · arXiv (Cornell University) · 2023
We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized. We give a $ \log^{1+o(1)}(n)$ approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS'88). Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest. We also use this to show other results, including an improved $ \log^{1+o(1)}(n)$ approximation for computing the pathwidth of a graph.
Cited by 1Open access
Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki · Discrete Mathematics · 2013
Cited by 16Open access
Rémy Belmonte, Kim, Eun Jung, Michael Lampis et al. · HAL (Le Centre pour la Communication Scientifique Directe) · 2020
To be published in proceedings of ESA 2020
Cited by 1
Hans L. Bodlaender A, Fedor V. Fomin B · 2002
Cited by 0
Nikhil Bansal, Dor Katzelnick, Roy Schwartz · 2024
We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized. We give a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\log^{1+o(1)}(n)$</tex> approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS'88). Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest. We also use this to show other results, including an improved <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\log^{1+o(1)}(n)$</tex> approximation for computing the pathwidth of a graph.
Cited by 0
Rodney G. Downey, Catherine McCartin · Lecture notes in computer science · 2004
Cited by 11
Jan Arne Telle · Electronic Notes in Discrete Mathematics · 2001
Cited by 2
Karol Suchan, Ioan Todinca · Lecture notes in computer science · 2007
Cited by 27
Jan Arne Telle · Discrete Applied Mathematics · 2004
Cited by 8
Rémy Belmonte, Kim, Eun Jung, Michael Lampis et al. · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2020
Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable to intractable? This type of question is by now very well-studied, but, somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes "for free". \nOur main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy First-Fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP-hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width.
Cited by 2Open access