:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Lanzinger, Matthias, Razgon, Igor, Unterberger, Daniel
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	https://arxiv.org/abs/2507.11080
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
by: Lanzinger, Matthias, et al.
Published: (2023)

Parameterised distance to local irregularity
by: Fioravantes, Foivos, et al.
Published: (2023)

Space Efficient Algorithms for Parameterised Problems
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

$O(n +f(k))$: Truly Linear FPT
by: Bumpus, Benjamin Merlin, et al.
Published: (2026)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Cuts and Gauges for Submodular Width
by: Lanzinger, Matthias
Published: (2026)

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

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
by: Beisegel, Jesse, et al.
Published: (2025)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
by: Beisegel, Jesse, et al.
Published: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

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

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
by: Esmer, Barış Can, et al.
Published: (2022)

Generalized Graph Packing Problems Parameterized by Treewidth
by: Esmer, Barış Can, et al.
Published: (2025)

On the Space Complexity of Online Convolution
by: Andersson, Joel Daniel, et al.
Published: (2025)

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

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

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

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Fractional Linear Matroid Matching is in quasi-NC
by: Gurjar, Rohit, et al.
Published: (2024)

Can You Link Up With Treewidth?
by: Curticapean, Radu, et al.
Published: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

On the Advantage of Adaptivity for Sampling with Cell Probes
by: Byramji, Farzan, et al.
Published: (2026)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
by: Beisegel, Jesse, et al.
Published: (2025)

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

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
by: Frei, Fabian, et al.
Published: (2024)

An alignment problem
by: McDaniel, Emma L., et al.
Published: (2024)

Colouring $(P_r+P_s)$-Free Graphs
by: Klimošová, Tereza, et al.
Published: (2018)

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

Efficient Approximation of Fractional Hypertree Width
by: Korchemna, Viktoriia, et al.
Published: (2024)

On Detecting $H$-Induced Minors for Small $H$
by: Eagling-Vose, Tala, et al.
Published: (2026)

Polynomial-Time Pseudodeterministic Construction of Primes
by: Chen, Lijie, et al.
Published: (2023)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)