Cover Image

Mim-Width is paraNP-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bergougnoux, Benjamin, Bonnet, Édouard, Duron, Julien
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics 68Q27 F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

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

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

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Symmetric-Difference (Degeneracy) and Signed Tree Models
by: Bonnet, Édouard, et al.
Published: (2024)

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
by: Bonnet, Édouard, et al.
Published: (2023)

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)

Adjacency Labeling Schemes for Small Classes
by: Bonnet, Édouard, et al.
Published: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
by: Jansen, Klaus, et al.
Published: (2024)

Fairness in the k-Server Problem
by: Daneshvaramoli, Mohammadreza, et al.
Published: (2025)

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

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
by: Fairbairn, David L., et al.
Published: (2024)

A New Temporal Interpretation of Cluster Editing
by: Bocci, Cristiano, et al.
Published: (2022)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
by: Hougardy, Stefan, et al.
Published: (2025)

Sparse Induced Subgraphs of Large Treewidth
by: Bonnet, Édouard
Published: (2024)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

A Decomposition Approach to the Weighted $k$-server Problem
by: Ayyadevara, Nikhil, et al.
Published: (2024)

Probabilistic Analysis of Edge Elimination for Euclidean TSP
by: Zhong, Xianghui
Published: (2018)

Computing parameters that generalize interval graphs using restricted modular partitions
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

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

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)

Color-Constrained Arborescences in Edge-Colored Digraphs
by: Ardra, P. S., et al.
Published: (2025)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
by: Bonnet, Édouard, et al.
Published: (2024)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
by: Komusiewicz, Christian, et al.
Published: (2023)

Online Bipartite Matching in the Probe-Commit Model
by: Borodin, Allan, et al.
Published: (2023)

Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
by: Ma, Will, et al.
Published: (2024)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
by: MacRury, Calum, et al.
Published: (2022)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

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

Moderately beyond clique-width: reduced component max-leaf and related parameters
by: Bonnet, Édouard, et al.
Published: (2026)

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

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
by: Bonnet, Édouard, et al.
Published: (2023)

Tight bounds on adjacency labels for monotone graph classes
by: Bonnet, Édouard, et al.
Published: (2023)

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
by: Bonnet, Édouard, et al.
Published: (2023)

A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
by: Sun, Hao
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)