Cover Image

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Knop, Dušan, Koutecký, Martin, Masařík, Tomáš, Toufar, Tomáš
Format:	Preprint
Published:	2017
Subjects:	Computational Complexity Logic in Computer Science F.2.2, G.2.2 F.2.2; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

Thin Tree Verification is coNP-Complete
by: Moayyedi, Alice
Published: (2025)

A Piecewise Approach for the Analysis of Exact Algorithms
by: Clinch, Katie, et al.
Published: (2024)

The characteristic polynomials of $r$-uniform hypercycles with length $l$
by: Bo, Dong, et al.
Published: (2025)

On Minimum Maximal Distance-k Matchings
by: Kartynnik, Yury, et al.
Published: (2016)

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Realizing temporal graphs from fastest travel times
by: Klobas, Nina, et al.
Published: (2023)

Minimizing an Uncrossed Collection of Drawings
by: Hliněný, Petr, et al.
Published: (2023)

General Strong Bound on the Uncrossed Number via a Tight Bound for the Maximum Uncrossed Subgraph Number
by: Charvy, Gaspard, et al.
Published: (2025)

Complexity of Firefighting on Graphs
by: Althoetmar, Julius, et al.
Published: (2025)

Drawing Reeb Graphs
by: Chambers, Erin, et al.
Published: (2025)

A Unified Framework for Weighted Hypergraphic Networks and Fractional Matching
by: Castera, Rémi, et al.
Published: (2026)

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

Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
by: Bok, Jan, et al.
Published: (2025)

On the Uncrossed Number of Graphs
by: Balko, Martin, et al.
Published: (2024)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity
by: Dreier, Jan, et al.
Published: (2026)

Large cliques and large independent sets: can they coexist?
by: Feige, Uriel, et al.
Published: (2025)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
by: Kowaluk, Miroslaw, et al.
Published: (2025)

Proving Unsatisfiability with Hitting Formulas
by: Filmus, Yuval, et al.
Published: (2023)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
by: Pilipczuk, Michał, et al.
Published: (2025)

On the Min-Max Star Partitioning Number
by: Feldmann, Sarah, et al.
Published: (2024)

Clock Synchronization Is Almost Impossible with Bounded Memory
by: Charron-Bost, Bernadette, et al.
Published: (2024)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

Measuring well quasi-ordered finitary powersets
by: Abriola, Sergio, et al.
Published: (2023)

Bidirectional Dijkstra's Algorithm is Instance-Optimal
by: Haeupler, Bernhard, et al.
Published: (2024)

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
by: Haeupler, Bernhard, et al.
Published: (2023)

Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
by: Bougeret, Marin, et al.
Published: (2024)

Kernelization dichotomies for hitting minors under structural parameterizations
by: Bougeret, Marin, et al.
Published: (2025)

Approximation Algorithms for Action-Reward Query-Commit Matching
by: Derakhshan, Mahsa, et al.
Published: (2026)

Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs
by: Balzotti, Lorenzo
Published: (2020)

The Spanning Ratio of the Directed $Θ_6$-Graph is 5
by: Bose, Prosenjit, et al.
Published: (2026)

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
by: Le, Hung, et al.
Published: (2023)

Map-Matching Queries under Fréchet Distance on Low-Density Spanners
by: Buchin, Kevin, et al.
Published: (2024)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
by: Liao, Chao, et al.
Published: (2022)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
by: Lobe, Elisabeth, et al.
Published: (2021)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
by: Kiatchaipipat, Nattapol, et al.
Published: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
by: Fritsch, Timo, et al.
Published: (2026)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
by: Gupta, Chetan, et al.
Published: (2025)