Cover Image

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lokshtanov, Daniel, Rzążewski, Paweł, Saurabh, Saket, Sharma, Roohani, Zehavi, Meirav
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity F.2.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
by: Agrawal, Akanksha, et al.
Published: (2024)

FPT Approximations for Connected Maximum Coverage
by: Inamdar, Tanmay, et al.
Published: (2026)

Subexponential Parameterized Algorithms for Hitting Subgraphs
by: Lokshtanov, Daniel, et al.
Published: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Balanced Substructures in Bicolored Graphs
by: Ardra, P. S., et al.
Published: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
by: Krithika, R., et al.
Published: (2023)

Efficient Approximation of Fractional Hypertree Width
by: Korchemna, Viktoriia, et al.
Published: (2024)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
by: Greilhuber, Jakob, et al.
Published: (2026)

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

An Optimal Randomized Algorithm for Finding the Saddlepoint
by: Dallant, Justin, et al.
Published: (2024)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

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

Replicability in High Dimensional Statistics
by: Hopkins, Max, et al.
Published: (2024)

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
by: Chauhan, Archit, et al.
Published: (2026)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
by: Sarriguren, Alfredo Goñi
Published: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
by: Esmer, Barış Can, et al.
Published: (2022)

Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
by: Chauhan, Archit, et al.
Published: (2025)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

On the formalization of the notion of an algorithm
by: Middelburg, C. A.
Published: (2024)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
by: Fomin, Fedor V., et al.
Published: (2025)

Parameterized Geometric Graph Modification with Disk Scaling
by: Fomin, Fedor V., et al.
Published: (2024)

Hybrid k-Clustering: Blending k-Median and k-Center
by: Fomin, Fedor V., 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)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
by: Saha, Barna, et al.
Published: (2024)

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

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Realizing temporal graphs from fastest travel times
by: Klobas, Nina, et al.
Published: (2023)

Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time
by: Hofman, Radoslaw
Published: (2006)

Constant congestion linkages in polynomially strong digraphs in polynomial time
by: Lopes, Raul, et al.
Published: (2024)

Learning Small Decision Trees with Few Outliers: A Parameterized Perspective
by: Gahlawat, Harmender, et al.
Published: (2025)

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

Complexity of Finding and Enumerating Interconnection Trees
by: Demange, Noé, et al.
Published: (2026)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
by: Chudnovsky, Maria, et al.
Published: (2024)