Results 1 to 10 of about 3,134 (121)
Parameterized Complexity of Vertex Splitting to Pathwidth at most 1 [PDF]
International Workshop on Graph-Theoretic Concepts in Computer Science, 2023 Motivated by the planarization of 2-layered straight-line drawings, we consider the problem of modifying a graph such that the resulting graph has pathwidth at most 1.
Jakob Baumann +2 more
openalex +3 more sources
First Order Logic on Pathwidth Revisited Again [PDF]
International Colloquium on Automata, Languages and Programming, 2022 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
Michael Lampis
semanticscholar +5 more sources
The Primal Pathwidth SETH [PDF]
arXiv.orgMotivated by the importance of dynamic programming (DP) in parameterized complexity, we consider several fine-grained questions, such as the following examples: (i) can Dominating Set be solved in time $(3-\epsilon)^{pw}n^{O(1)}$?
Michael Lampis
semanticscholar +3 more sources
The treewidth and pathwidth of graph unions [PDF]
SIAM Journal on Discrete Mathematics, 2022 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
Bogdan Alecu +5 more
openalex +3 more sources
On Approximating Cutwidth and Pathwidth [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 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.
Nikhil Bansal +2 more
openalex +3 more sources
Two Results on Layered Pathwidth and Linear Layouts [PDF]
J. Graph Algorithms Appl., 2021 Layered pathwidth is a new graph parameter studied by Bannister et al (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts.
Vida Dujmović, Pat Morin, Céline Yelle
openalex +2 more sources
Tight Bound on Treedepth in Terms of Pathwidth and Longest Path
Combinatorica, 2023 We show that every graph with pathwidth strictly less than a that contains no path on 2b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs ...
Meike Hatzel +5 more
openalex +3 more sources
Minor-Closed Graph Classes with Bounded Layered Pathwidth [PDF]
SIAM Journal on Discrete Mathematics, 2020 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 generalises a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if ...
Vida Dujmović +4 more
openalex +3 more sources
Approximating Pathwidth for Graphs of Small Treewidth [PDF]
ACM-SIAM Symposium on Discrete 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.
Carla Groenland +3 more
openalex +3 more sources
$b$-Coloring Parameterized by Pathwidth is XNLP-complete [PDF]
arXiv.org, 2022 We show that the $b$-Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathwidth
Lars Jaffke +2 more
openalex +3 more sources