Results 1 to 10 of about 973 (119)
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
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
semanticscholar +3 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)}$?
M. Lampis
semanticscholar +3 more sources
Tight Bound on Treedepth in Terms of Pathwidth and Longest Path [PDF]
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
semanticscholar +2 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
semanticscholar +3 more sources
Two Results on Layered Pathwidth and Linear Layouts [PDF]
J. Graph Algorithms Appl., 2020 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'c, Pat Morin, Céline Yelle
semanticscholar +2 more sources
Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number [PDF]
International Symposium on Parameterized and Exact ComputationIn the \textsc{Geodetic Set} problem, the input consists of a graph $G$ and a positive integer $k$. The goal is to determine whether there exists a subset $S$ of vertices of size $k$ such that every vertex in the graph is included in a shortest path ...
P. Tale
semanticscholar +2 more sources
Minor-closed graph classes with bounded layered pathwidth [PDF]
SIAM Journal on Discrete Mathematics, 2018 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 ...
V. Dujmović +4 more
semanticscholar +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
L. Jaffke +2 more
semanticscholar +3 more sources
Approximating Pathwidth for Graphs of Small Treewidth [PDF]
ACM-SIAM Symposium on Discrete Algorithms, 2020 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
semanticscholar +3 more sources