Cover Image

A Fixed Parameter Tractable Approach for Solving the Vertex Cover Problem in Polynomial Time Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Tayal, Mumuksh
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Fixed-Parameter Tractability of Weighted 0-1 Timed Matching Problem on Temporal Graphs
by: Kumar, Rinku, et al.
Published: (2025)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

Fixed-Parameter Tractable Submodular Maximization over a Matroid
by: Nematollahi, Shamisa, et al.
Published: (2025)

Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
by: Mizutani, Yosuke, et al.
Published: (2024)

Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons
by: Sharma, Vidya Sagar
Published: (2023)

Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
by: Pintér, József, et al.
Published: (2026)

Enumeration kernels for Vertex Cover and Feedback Vertex Set
by: Bougeret, Marin, et al.
Published: (2025)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Capacitated Partition Vertex Cover and Partition Edge Cover
by: Dabas, Rajni, et al.
Published: (2025)

Weighted Partition Vertex and Edge Cover
by: Dabas, Rajni, et al.
Published: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
by: Chen, Yong, et al.
Published: (2025)

Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
by: Haviv, Ishay
Published: (2022)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

Parameterized Algorithms for Minimum Sum Vertex Cover
by: Aute, Shubhada, et al.
Published: (2024)

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
by: Hamm, Thekla, et al.
Published: (2022)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
by: Lehner, Lisa, et al.
Published: (2025)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
by: Clinch, Katie, et al.
Published: (2025)

A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton
by: Sharma, Vidya Sagar
Published: (2023)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

A Fast-Converging Decentralized Approach to the Weighted Minimum Vertex Cover Problem
by: Mordacchini, Matteo, et al.
Published: (2025)

The Connected k-Vertex One-Center Problem on Graphs
by: Zhang, Jingru
Published: (2024)

Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
by: Goldmann, Lito, et al.
Published: (2023)

Bicluster Editing with Overlaps: A Vertex Splitting Approach
by: Abu-Khzam, Faisal N., et al.
Published: (2025)

Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation
by: de Colnet, Alexis, et al.
Published: (2026)

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
by: Baste, Julien, et al.
Published: (2019)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
by: Bampis, Evripidis, et al.
Published: (2025)

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
by: Jourdan, Ben, et al.
Published: (2024)

New Approximations for Temporal Vertex Cover on Always Star Temporal Graphs
by: Heck, Sophia, et al.
Published: (2026)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
by: Fischer, Olivier, et al.
Published: (2025)

A more versatile model for enumerative kernelization: a case study for Vertex Cover
by: Bougeret, Marin, et al.
Published: (2026)

Space Complexity of Vertex Connectivity Oracles
by: Pettie, Seth, et al.
Published: (2022)

A faster algorithm for Vertex Cover parameterized by solution size
by: Harris, David G., et al.
Published: (2022)

Optimising Cylindrical Algebraic Coverings for use in SMT by Solving a Set Covering Problem with Reasons
by: Babatunde, Abiola, et al.
Published: (2026)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
by: Chen, Kuowen, et al.
Published: (2025)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
by: Davies-Peck, Peter
Published: (2026)