Exploring the gap between treedepth and vertex cover through vertex integrity

DOI10.1016/j.tcs.2022.03.021OpenAlexW3123457922MaRDI QIDQ5918674

Yasuaki Kobayashi, Tatsuya Gima, Yota Otachi, Masashi Kiyomi, Tesshu Hanaka

Publication date: 10 May 2022

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

Full work available at URL: https://arxiv.org/abs/2101.09414

zbMATH Keywords

vertex cover numbervertex integritytreedepth

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Problems hard for treewidth but easy for stable gonality ⋮ Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The parameterised complexity of list problems on graphs of bounded treewidth
• Sparsity. Graphs, structures, and algorithms
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• On the complexity of some colorful problems parameterized by treewidth
• Improved upper bounds for vertex cover
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• On the computational complexity of vertex integrity and component order connectivity
• The Steiner forest problem revisited
• An application of simultaneous diophantine approximation in combinatorial optimization
• Balanced vertex-orderings of graphs
• Parameterized complexity of length-bounded cuts and multicuts
• The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
• Bin packing with fixed number of bins revisited
• Linear time solvable optimization problems on graphs of bounded clique-width
• Metric dimension parameterized by treewidth
• The graph motif problem parameterized by the structure of the input graph
• Imbalance is fixed parameter tractable
• Maximum common induced subgraph parameterized by vertex cover
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Monadic second order logic on graphs with local cardinality constraints
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Integer Programming with a Fixed Number of Variables
• On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
• Easy problems for tree-decomposable graphs
• Capacitated Domination and Covering: A Parameterized Perspective
• Graph Layout Problems Parameterized by Vertex Cover
• What Makes Equitable Connected Partition Easy
• Minkowski's Convex Body Theorem and Integer Programming
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Approximating rank-width and clique-width quickly
• New Results on Directed Edge Dominating Set
• A Faster Parameterized Algorithm for Treedepth
• Metric Dimension of Bounded Tree-length Graphs
• On the Relationship Between Clique-Width and Treewidth
• Parameterized Algorithms
• Imbalance parameterized by twin cover revisited
• Subgraph isomorphism on graph classes that exclude a substructure
• Parameterized Complexity of Geodetic Set

This page was built for publication: Exploring the gap between treedepth and vertex cover through vertex integrity