Improved upper bounds for vertex cover

From MaRDI portal

Publication:708228

Jump to:navigation, search

DOI10.1016/j.tcs.2010.06.026zbMath1205.05217OpenAlexW2059451253MaRDI QIDQ708228

Iyad A. Kanj, Ge Xia, Jian'er Chen

Publication date: 11 October 2010

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.026

zbMATH Keywords

vertex cover NP-complete problem parameterized algorithm branch-and-search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the ordered list subgraph embedding problems ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Faster exact algorithms for some terminal set problems ⋮ An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem ⋮ A parameterized complexity view on collapsing \(k\)-cores ⋮ Compactors for parameterized counting problems ⋮ Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics ⋮ An improved deterministic parameterized algorithm for cactus vertex deletion ⋮ Parameterized Algorithms for Queue Layouts ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ A Basic Parameterized Complexity Primer ⋮ Backdoors to Satisfaction ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Parameterized Power Vertex Cover ⋮ A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition ⋮ Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number ⋮ Fixed-parameter tractability for book drawing with bounded number of crossings per edge ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ A multivariate framework for weighted FPT algorithms ⋮ Winner determination algorithms for graph games with matching structures ⋮ Parameterized and exact algorithms for class domination coloring ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Parameterized analysis and crossing minimization problems ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion} ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Approximation for vertex cover in \(\beta\)-conflict graphs ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Parameterized complexity of vertex deletion into perfect graph classes ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Parameterized approximation via fidelity preserving transformations ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ A note on the parameterized complexity of unordered maximum tree orientation ⋮ Unnamed Item ⋮ On the \(d\)-claw vertex deletion problem ⋮ Proper interval vertex deletion ⋮ The many facets of upper domination ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Parameterized algorithms for book embedding problems ⋮ Local search: is brute-force avoidable? ⋮ Solving vertex cover in polynomial time on hyperbolic random graphs ⋮ Maximum common induced subgraph parameterized by vertex cover ⋮ On computing the minimum 3-path vertex cover and dissociation number of graphs ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ Confronting intractability via parameters ⋮ Backdoors for linear temporal logic ⋮ Implicit branching and parameterized partial cover problems ⋮ Parameterized Algorithms for Book Embedding Problems ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Complexity of conflict-free colorings of graphs ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ On optimal approximability results for computing the strong metric dimension ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ On the complexity of wafer-to-wafer integration ⋮ Parameterized complexity of \textsc{maximum edge colorable subgraph} ⋮ On families of categorial grammars of bounded value, their learnability and related complexity questions ⋮ Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover ⋮ Unnamed Item ⋮ Maximum independent sets near the upper bound ⋮ Unnamed Item ⋮ Dynamic parameterized problems ⋮ On the Complexity Landscape of the Domination Chain ⋮ Extended formulations for vertex cover ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ The Monotone Circuit Value Problem with Bounded Genus Is in NC ⋮ Strong Backdoors for Default Logic ⋮ Parameterized Complexity of Vertex Deletion into Perfect Graph Classes ⋮ Quick separation in chordal and split graphs ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Unnamed Item ⋮ Efficient parallel algorithms for parameterized problems ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ Parameterized complexity of maximum edge colorable subgraph ⋮ Worst-case analysis of clique MIPs ⋮ Backdoors to tractable answer set programming ⋮ Parameterized Algorithms for Queue Layouts ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization ⋮ Obtaining matrices with the consecutive ones property by row deletions ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set ⋮ Above guarantee parameterization for vertex cover on graphs with maximum degree 4 ⋮ A refined branching algorithm for the maximum satisfiability problem ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ On the complexity of the storyplan problem ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ Reducing the vertex cover number via edge contractions ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Structural parameterization of alliance problems ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Slightly Superexponential Parameterized Problems ⋮ Winner determination algorithms for graph games with matching structures ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ On the \(d\)-claw vertex deletion problem ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ On finding separators in temporal split and permutation graphs ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size

Uses Software

DIMACS

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:708228&oldid=12625450"