Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 467 papers for “Pathwidth”

Randomly Coloring Graphs of Logarithmically Bounded Pathwidth

Venkatesan Guruswami · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016

We consider the problem of sampling a proper k-coloring of a graph of maximal degree Delta uniformly at random. We describe a new Markov chain for sampling colorings, and show that it mixes rapidly on graphs of logarithmically bounded pathwidth if k >=(1+epsilon)Delta, for any epsilon>0, using a hybrid paths argument.

Cited by 16Open access

Pathwidth of 2-Layer $k$-Planar Graphs

Okada, Yuto · ArXiv.org · 2025

A bipartite graph $G = (X \cup Y, E)$ is a 2-layer $k$-planar graph if it admits a drawing on the plane such that the vertices in $X$ and $Y$ are placed on two parallel lines respectively, edges are drawn as straight-line segments, and every edge involves at most $k$ crossings. Angelini, Da Lozzo, Förster, and Schneck [GD 2020; Comput. J., 2024] showed that every 2-layer $k$-planar graph has pathwidth at most $k + 1$. In this paper, we show that this bound is sharp by giving a 2-layer $k$-planar graph with pathwidth $k + 1$ for every $k \geq 0$. This improves their lower bound of $(k+3)/2$.

Cited by 0Open access

Nondeterministic Graph Searching: From Pathwidth to Treewidth

Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse · 2005

Abstract. We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q-branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q ≥ 0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.

Cited by 0

Fragmentos de CPDL+ mediante propiedades de pathwidth

Schiavinato, Mauro Luis · Repositorio Digital Institucional de la Universidad de Buenos Aires (Universidad de Buenos Aires) · 2024

En este trabajo nos centramos en CPDL+, un lenguaje recientemente definido que extiende a PDL, una lógica modal ya conocida y ampliamente estudiada. Sobre esta nueva lógica estudiamos una jerarquización del lenguaje basado en propiedades de pathwidth asociados a los grafos subyacentes de ciertas expresiones que este lenguaje posee. Esta jerarquización es comparable y análoga a la jerarquización de CPDL+ basada en propiedades de treewidth con la que se definió originalmente. En un principio, nuestro problema se basaba en hacer una comparación de expresividad de varios fragmentos de CPDL+, pero varias propiedades relacionadas con teoría de modelos y juegos de simulación fueron surgiendo a medida que este estudio se fue desarrollando. Finalmente, demostramos que el criterio de simulación estudiado para la jerarquía de treewidth también sirve para pathwidth, con algunas modificaciones semánticas.

Cited by 0Open access

The Treewidth and Pathwidth of Graph Unions

Bogdan Alecu, Vadim Lozin, Daniel A. Quiroz et al. · SIAM Journal on Discrete Mathematics · 2024

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

Cited by 2Open access

Approximating Pathwidth for Graphs of Small Treewidth

Carla Groenland, Gwenaël Joret, Wojciech Nadara et al. · ACM Transactions on Algorithms · 2022

We describe a polynomial-time algorithm which, given a graph G with treewidth t , approximates the pathwidth of G to within a ratio of \(O(t\sqrt {\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.

Cited by 10Open access

Bandwidth and pathwidth of three-dimensional grids

Yota Otachi, Ryohei Suda · arXiv (Cornell University) · 2011

We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors.

Cited by 0Open access

First Order Logic on Pathwidth Revisited Again

Michael Lampis · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2023

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.
\nIn 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.

Cited by 1Open access

On the Treewidth and Pathwidth of Permutation Graphs

T. Kloks, H. Bodlaender, T. Kloks et al. · 1992

In this paper we discuss the problem of finding the treewidth and pathwidth of permutation graphs. If G[r] is a permutation graph with treewidth k, then we show that the pathwidth of G[r] is at most 2k, and we give an algo- rithm which constructs a path-decomposition with width at most 2k in time O(nk). We assume that the permutation r is given. For permutation graphs of which the treewidth is bounded by some constant, this result, together with previous results ([9], [15]), shows that the treewidth and pathwidth can be computed in linear time.

Cited by 0

A Linear Algorithm for the Pathwidth of Trees

Petra Scheffler · 1990

The pathwidth is a graph parameter only recently studied but closely related to other characteristics of graphs like tree, band- or cutwidth, interval thickness or search number ([S]). The graphs considered here are finite, undirected and simple. First the preliminaries are given. Section 2 contains our main results on the pathwidth of trees, the basis for the algorithm described in section 3.

Cited by 42