Cover Image

Finding Induced Subgraphs from Graphs with Small Mim-Width

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Otachi, Yota, Suzuki, Akira, Tamura, Yuma
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
by: Hanaka, Tesshu, et al.
Published: (2025)

Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules
by: Suga, Tatsuhiro, et al.
Published: (2025)

Spanning tree congestion of proper interval graphs
by: Otachi, Yota
Published: (2026)

Biclique Reconfiguration in Bipartite Graphs
by: Otachi, Yota, et al.
Published: (2026)

Finding Order-Preserving Subgraphs
by: Imamura, Haruya, et al.
Published: (2025)

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
by: Cardinal, Jean, et al.
Published: (2026)

Sequentially Swapping Tokens: Further on Graph Classes
by: Kiya, Hironori, et al.
Published: (2022)

Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
by: Kokai, Toranosuke, et al.
Published: (2025)

Hitting Geodesic Intervals in Structurally Restricted Graphs
by: Gima, Tatsuya, et al.
Published: (2025)

Forcing a unique minimum spanning tree and a unique shortest path
by: Gima, Tatsuya, et al.
Published: (2025)

Treewidth of the $n \times n$ toroidal grid
by: Gima, Tatsuya, et al.
Published: (2026)

Finding Small Complete Subgraphs Efficiently
by: Chen, Ke, et al.
Published: (2023)

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

Dichotomies for Tree Minor Containment with Structural Parameters
by: Gima, Tatsuya, et al.
Published: (2023)

An improved spectral lower bound of treewidth
by: Gima, Tatsuya, et al.
Published: (2024)

Computing diverse pair of solutions for tractable SAT
by: Gima, Tatsuya, et al.
Published: (2024)

Structural Parameterizations of Vertex Integrity
by: Gima, Tatsuya, et al.
Published: (2023)

Coloring Reconfiguration under Color Swapping
by: Fuchs, Janosch, et al.
Published: (2025)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

The Complexity Landscape of Dynamic Distributed Subgraph Finding
by: Chang, Yi-Jun, et al.
Published: (2024)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
by: Curticapean, Radu, et al.
Published: (2025)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
by: Curticapean, Radu, et al.
Published: (2024)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
by: Norose, Ryoma, et al.
Published: (2024)

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

Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing
by: Eppstein, David, et al.
Published: (2025)

Isomorphism for Tournaments of Small Twin Width
by: Grohe, Martin, et al.
Published: (2023)

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

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Graph Reconstruction from Noisy Random Subgraphs
by: McGregor, Andrew, et al.
Published: (2024)

Broadcasting under Structural Restrictions
by: Egami, Yudai, et al.
Published: (2025)

Destroying Densest Subgraphs is Hard
by: Bazgan, Cristina, et al.
Published: (2024)

Forbidden Subgraph Problems with Predictions
by: Böckenhauer, Hans-Joachim, et al.
Published: (2025)

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

Width Parameters for Minimum Flow Decomposition
by: Grigorjew, Andreas, et al.
Published: (2024)

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

Distributed Subgraph Finding: Progress and Challenges
by: Censor-Hillel, Keren
Published: (2022)

Counting Cohesive Subgraphs with Hereditary Properties
by: Li, Rong-Hua, et al.
Published: (2024)