Cover Image

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Agrawal, Akanksha, Lima, Paloma T., Lokshtanov, Daniel, Rzążewski, Pawel, Saurabh, Saket, Sharma, Roohani
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms 68Q25, 05C85 F.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
by: Cui, Jinchuan, et al.
Published: (2022)

Parameterized Complexity of Directed Traveling Salesman Problem
by: Blažej, Václav, et al.
Published: (2025)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
by: Huber, Michael Kiran
Published: (2024)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
by: Gartland, Peter, et al.
Published: (2023)

Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
by: Nasre, Meghana, et al.
Published: (2023)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

Reconfiguring homomorphisms to reflexive graphs via a simple reduction
by: Mühlenthaler, Moritz, et al.
Published: (2024)

Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph
by: Li, Xingfu, et al.
Published: (2026)

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
by: Gu, Qian-Ping, et al.
Published: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
by: Bojikian, Narek, et al.
Published: (2024)

Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
by: Wang, Chen, et al.
Published: (2023)

Steiner Tree Parameterized by Multiway Cut and Even Less
by: Jansen, Bart M. P., et al.
Published: (2024)

Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs
by: Morse, Gregory, et al.
Published: (2026)

The Upper Clique Transversal Problem
by: Milanič, Martin, et al.
Published: (2023)

Sublinear-Time Computation in the Presence of Online Erasures
by: Kalemaj, Iden, et al.
Published: (2021)

Overlapping Biclustering
by: Bentert, Matthias, et al.
Published: (2025)

Simple minimally unsatisfiable subsets of 2-CNFs
by: Kullmann, Oliver, et al.
Published: (2026)

Maximum Matchings in Geometric Intersection Graphs
by: Bonnet, Édouard, et al.
Published: (2019)

Tree decompositions meet induced matchings: beyond Max Weight Independent Set
by: Lima, Paloma T., et al.
Published: (2024)

Parameterized Saga of First-Fit and Last-Fit Coloring
by: Agrawal, Akanksha, et al.
Published: (2024)

A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
by: Jiang, Xinwen, et al.
Published: (2021)

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
by: Datta, Swarnalipa, et al.
Published: (2026)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
by: Oum, Sang-il, et al.
Published: (2026)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
by: Bonnet, Édouard, et al.
Published: (2026)

Path Contraction Faster than $2^n$
by: Agrawal, Akanksha, et al.
Published: (2025)

Shortest Paths without a Map, but with an Entropic Regularizer
by: Bubeck, Sébastien, et al.
Published: (2022)

ARRIVAL: Recursive Framework & $\ell_1$-Contraction
by: Haslebacher, Sebastian
Published: (2025)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
by: Liu, Bowen
Published: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
by: Göbel, Andreas, et al.
Published: (2025)

Perfect Edge Domination in $P_6$-free Graphs and in Graphs Without Efficient Edge Dominating Sets
by: Grippo, Luciano N., et al.
Published: (2025)

An Algorithm to Find Sums of Powers of Consecutive Primes
by: O'Sullivan, Cathal, et al.
Published: (2022)

On Solving Simple Curved Nonograms
by: Löffler, Maarten, et al.
Published: (2025)