Parameterized complexity of vertex splitting to pathwidth at most 1

DOI10.1016/J.TCS.2024.114928MaRDI QIDQ6639742zbMATH OpenFDO

Authors Ignaz Rutter

Publication date 18 November 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114928

zbMATH Keywords

2-layer drawingalgorithmsbranching algorithmcomputational complexityfixed-parameterized tractabilitygraphskernelizationpathwidth 1vertex splitting

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A quartic kernel for pathwidth-one vertex deletion
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion
• Vertex deletion on split graphs: beyond 4-hitting set
• Parameterized complexity of vertex colouring

Cites work

• A 4k^2 kernel for feedback vertex set
• A linear time algorithm for finding tree-decompositions of small treewidth
• A near-optimal planarization algorithm
• A quartic kernel for pathwidth-one vertex deletion
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• Easy problems for tree-decomposable graphs
• Faster algorithm for pathwidth one vertex deletion
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 1262805 (Why is no real title available?)
• scientific article; zbMATH DE number 512967 (Why is no real title available?)
• Obtaining a Planar Graph by Vertex Deletion
• Parameterized algorithms
• Planarity Allowing Few Error Vertices in Linear Time
• Reducibility among combinatorial problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(1)

• Improved kernelization and fixed-parameter algorithm for bipartite one-sided vertex explosion

This page was built for publication: Parameterized complexity of vertex splitting to pathwidth at most 1

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6639742)