Cover Image

Hardness and Approximation for Coloring Digraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chalermsook, Parinya, Gahlawat, Harmender, Klingelhoefer, Felix, Newman, Alantha, Tang, Chaoliang
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Coloring tournaments with few colors: Algorithms and complexity
by: Klingelhoefer, Felix, et al.
Published: (2023)

Shortcuts and Transitive-Closure Spanners Approximation
by: Chalermsook, Parinya, et al.
Published: (2025)

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

On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers
by: Chalermsook, Parinya, et al.
Published: (2025)

A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three
by: Chalermsook, Parinya, et al.
Published: (2025)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
by: Gahlawat, Harmender, et al.
Published: (2025)

Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
by: Fioravantes, Foivos, et al.
Published: (2025)

Improved linearly ordered colorings of hypergraphs via SDP rounding
by: Louis, Anand, et al.
Published: (2024)

Approximation Algorithms for Digraph Width Parameters
by: Kintali, Shiva, et al.
Published: (2011)

Understanding the Cluster LP for Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2024)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
by: Włodarczyk, Michał
Published: (2024)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
by: Foucaud, Florent, et al.
Published: (2026)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
by: Bourneuf, Romain, et al.
Published: (2025)

Stochastic Embedding of Digraphs into DAGs
by: Filtser, Arnold
Published: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Node-Weighted Multicut in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2026)

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)

Approximations and Hardness of Packing Partially Ordered Items
by: Doron-Arad, Ilan, et al.
Published: (2024)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

Fully Dynamic Strongly Connected Components in Planar Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Automating the Search for Small Hard Examples to Approximation Algorithms
by: Sharma, Eklavya
Published: (2025)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
by: Lokshtanov, Daniel, et al.
Published: (2024)

On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
by: Albers, Susanne, et al.
Published: (2025)

Integer and Unsplittable Multiflows in Series-Parallel Digraphs
by: Almoghrabi, Mohammed Majthoub, et al.
Published: (2024)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
by: Yamano, Ryosuke, et al.
Published: (2026)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
by: Lachish, Oded, et al.
Published: (2026)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Upward Book Embeddings of Partitioned Digraphs
by: Da Lozzo, Giordano, et al.
Published: (2026)

Improved Hardness-of-Approximation for Token Swapping
by: Hiken, Sam, et al.
Published: (2024)

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
by: Arndt, Stephen, et al.
Published: (2026)

Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions
by: Horowicz, Noam, et al.
Published: (2025)