Exact Algorithms via Multivariate Subroutines

DOI10.4230/LIPICS.ICALP.2017.69zbMATH Open1441.68181arXiv1704.07982OpenAlexW2963608970MaRDI QIDQ5111400FDOQ5111400

Publication date: 27 May 2020

Abstract: We consider the family of

P h i

-Subset problems, where the input consists of an instance

I

of size

N

over a universe

U_{I}

of size

n

and the task is to check whether the universe contains a subset with property

P h i

(e.g.,

P h i

could be the property of being a feedback vertex set for the input graph of size at most

k

). Our main tool is a simple randomized algorithm which solves

P h i

-Subset in time

(1 + b - f r a c 1 c)^{n} N^{O (1)}

, provided that there is an algorithm for the

P h i

-Extension problem with running time

b^{n - | X |} c^{k} N^{O (1)}

. Here, the input for

P h i

-Extension is an instance

I

of size

N

over a universe

U_{I}

of size

n

, a subset

X s u b s e t e q U_{I}

, and an integer

k

, and the task is to check whether there is a set

Y

with

X s u b s e t e q Y s u b s e t e q U_{I}

and

| Y s e t m i n u s X | l e k

with property

P h i

. We derandomize this algorithm at the cost of increasing the running time by a subexponential factor in

n

, and we adapt it to the enumeration setting where we need to enumerate all subsets of the universe with property

P h i

. This generalizes the results of Fomin et al. [STOC 2016] who proved the case where

b = 1

. As case studies, we use these results to design faster deterministic algorithms for: - checking whether a graph has a feedback vertex set of size at most

k

- enumerating all minimal feedback vertex sets - enumerating all minimal vertex covers of size at most

k

, and - enumerating all minimal 3-hitting sets. We obtain these results by deriving new

b^{n - | X |} c^{k} N^{O (1)}

-time algorithms for the corresponding

P h i

-Extension problems (or enumeration variant). In some cases, this is done by adapting the analysis of an existing algorithm, or in other cases by designing a new algorithm. Our analyses are based on Measure and Conquer, but the value to minimize,

1 + b - f r a c 1 c

, is unconventional and requires non-convex optimization.

Full work available at URL: https://arxiv.org/abs/1704.07982

zbMATH Keywords

feedback vertex set hitting set enumeration algorithms exponential-time algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Cited In (1)

Title not available (Why is that?)

This page was built for publication: Exact Algorithms via Multivariate Subroutines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111400)