Cover Image

EPTAS for Hard Graph Cut Problems for Dense Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Deguchi, Kaisei, Kawarabayashi, Ken-ichi, Mori, Hiroaki
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Discrete Mathematics Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Graph Coloring for $k$-Colorable Graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Hardness of Burning Number Problem on Regular Graphs
by: Antony, Dhanyamol, et al.
Published: (2026)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
by: Dudeja, Aditi, et al.
Published: (2024)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
by: Lucke, Felicia, et al.
Published: (2024)

Extending Ghouila-Houri's Characterization of Comparability Graphs to Temporal Graphs
by: Charbit, Pierre, et al.
Published: (2025)

Finding $d$-Cuts in Probe $H$-Free Graphs
by: Dabrowski, Konrad K., et al.
Published: (2025)

$α_i$-Metric Graphs: Hyperbolicity
by: Dragan, Feodor F., et al.
Published: (2024)

Palette Sparsification for Graphs with Sparse Neighborhoods
by: Dhawan, Abhishek
Published: (2024)

Colouring Probe $H$-Free Graphs
by: Paulusma, Daniël, et al.
Published: (2025)

Light Edge Fault Tolerant Graph Spanners
by: Bodwin, Greg, et al.
Published: (2025)

Bounding Width on Graph Classes of Constant Diameter
by: Dabrowski, Konrad K., et al.
Published: (2025)

Sandwich Monotonicity and the Recognition of Weighted Graph Classes
by: Beisegel, Jesse, et al.
Published: (2025)

Graph parameters that are coarsely equivalent to path-length
by: Dragan, Feodor F., et al.
Published: (2025)

Thin Trees via $k$-Respecting Cut Identities
by: Daga, Mohit
Published: (2025)

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
by: Holtgrefe, Niels, et al.
Published: (2024)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
by: Neuen, Daniel
Published: (2020)

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
by: Srinivasan, Eshwar, et al.
Published: (2026)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Tree Independence Number IV. Even-hole-free Graphs
by: Chudnovsky, Maria, et al.
Published: (2024)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
by: Chen, Yu, et al.
Published: (2023)

On the sizes of BDDs and ZDDs representing matroids
by: Emoto, Hiromi, et al.
Published: (2024)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, et al.
Published: (2025)

Graph Search Trees and the Intermezzo Problem
by: Beisegel, Jesse, et al.
Published: (2024)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
by: Ghanbari, Babak, et al.
Published: (2026)

Solving Problems on Generalized Convex Graphs via Mim-Width
by: Bonomo-Braberman, Flavia, et al.
Published: (2020)

The Strong Birthday Problem Revisited
by: Tripathy, Chijul B.
Published: (2025)

Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem
by: Fujiwara, Hiroshi, et al.
Published: (2025)

Problems on Group-labeled Matroid Bases
by: Hörsch, Florian, et al.
Published: (2024)

On The Maximum Linear Arrangement Problem for Trees
by: Alemany-Puig, Lluís, et al.
Published: (2023)

An Algebraic Approach to the Longest Path Problem
by: Khazali, Omar Al -
Published: (2023)

The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring
by: Inoue, Yuta, et al.
Published: (2026)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
by: Paschalidis, Phevos, et al.
Published: (2023)

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
by: Ameli, Afrouz Jabal, et al.
Published: (2026)

Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem
by: Shook, James M., et al.
Published: (2025)

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
by: Eagling-Vose, Tala, et al.
Published: (2025)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
by: Beisegel, Jesse, et al.
Published: (2025)