Randomised enumeration of small witnesses using a decision oracle

DOI10.1007/s00453-018-0404-yzbMath1411.68049OpenAlexW2962790604MaRDI QIDQ1725640

Kitty Meeks

Publication date: 14 February 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0404-y

zbMATH Keywords

randomized algorithmsparameterized complexityenumeration algorithmscolor codingapproximate enumeration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20)

Related Items (2)

Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• The parameterised complexity of counting connected subgraphs and graph motifs
• Narrow sieves for parameterized paths and packings
• Parametrized complexity theory.
• Parameterized Enumeration for Modification Problems
• Some Hard Families of Parameterized Counting Problems
• Paradigms for Parameterized Enumeration
• Fast Witness Extraction Using a Decision Oracle
• Probably optimal graph motifs
• Color-coding
• The Parameterized Complexity of Counting Problems
• Engineering Motif Search for Large Graphs
• Counting Matchings of Size k Is $\sharp$ W[1-Hard]
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem

This page was built for publication: Randomised enumeration of small witnesses using a decision oracle