Cover Image

Independence-Number Parameterized Space Complexity for Directed Connectivity Certificate

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Ho-Lin, Cheung, Tsun Ming, Lin, Peng-Ting, Tsai, Meng-Tsung
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

Efficient Streaming Algorithms for Two-Dimensional Congruence Testing and Geometric Hashing
by: Chang, Yen-Cheng, et al.
Published: (2026)

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

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

Parameterized Complexity of Efficient Sortation
by: Ganian, Robert, et al.
Published: (2024)

Parameterized Complexity of Simultaneous Planarity
by: Fink, Simon D., et al.
Published: (2023)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
by: Anand, Aditya, et al.
Published: (2025)

Space Complexity of Vertex Connectivity Oracles
by: Pettie, Seth, et al.
Published: (2022)

The Parameterized Complexity Landscape of the Unsplittable Flow Problem
by: Ganian, Robert, et al.
Published: (2024)

Parameterized Complexity of Finding Dissimilar Shortest Paths
by: Funayama, Ryo, et al.
Published: (2024)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
by: Sawettamalya, Pachara, et al.
Published: (2025)

Parameterized Complexity of Directed Traveling Salesman Problem
by: Blažej, Václav, et al.
Published: (2025)

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
by: Eiben, Eduard, et al.
Published: (2024)

EF(X) Orientations: A Parameterized Complexity Perspective
by: Kanellopoulos, Sotiris, et al.
Published: (2025)

Parameterized Complexity of MinCSP over the Point Algebra
by: Osipov, George, et al.
Published: (2023)

On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
by: Blažej, Václav, et al.
Published: (2024)

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
by: Bergougnoux, Benjamin, et al.
Published: (2023)

New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
by: Ameli, Afrouz Jabal, et al.
Published: (2026)

A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
by: Xiong, Ziliang, et al.
Published: (2024)

Parameterized Complexity of Streaming Diameter and Connectivity Problems
by: Oostveen, Jelle J., et al.
Published: (2022)

Improved and Parameterized Algorithms for Online Multi-level Aggregation: A Memory-based Approach
by: Turoczy, Alexander, et al.
Published: (2025)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
by: Bodlaender, Hans L., et al.
Published: (2026)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
by: Parter, Merav, et al.
Published: (2024)

Treewidth Parameterized by Feedback Vertex Number
by: Molter, Hendrik, et al.
Published: (2025)

Faster Parameterized Vertex Multicut
by: Chu, Huairui, et al.
Published: (2026)

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

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
by: Goyal, Dishant, et al.
Published: (2024)

Bandwidth Parameterized by Cluster Vertex Deletion Number
by: Gima, Tatsuya, et al.
Published: (2023)

Space Complexity of Minimum Cut Problems in Single-Pass Streams
by: Ding, Matthew, et al.
Published: (2024)

Computing Tree Decompositions with Small Independence Number
by: Dallard, Clément, et al.
Published: (2022)

Parameterized Complexity of Vehicle Routing
by: Döring, Michelle, et al.
Published: (2025)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

On the Parameterized Complexity of Diverse SAT
by: Misra, Neeldhara, et al.
Published: (2024)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
by: Marin, Malory
Published: (2025)

On the Number of Non-equivalent Parameterized Squares in a String
by: Hamai, Rikuya, et al.
Published: (2024)

Approximating Directed Connectivity in Almost-Linear Time
by: Quanrud, Kent
Published: (2025)

Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
by: Bshouty, Nader H., et al.
Published: (2026)

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
by: Casel, Katrin, et al.
Published: (2019)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

The Parameterized Complexity of Extending Stack Layouts
by: Depian, Thomas, et al.
Published: (2024)