skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms

Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav

ACM transactions on algorithms, 2020-06, Vol.16 (3), p.1-31 [Periódico revisado por pares]

ACM

Texto completo disponível

Citações Citado por
  • Título:
    Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
  • Autor: Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav
  • Assuntos: Independece covering family ; parameterized algorithms ; stable multicut ; stable OCT ; stable s-t separator
  • É parte de: ACM transactions on algorithms, 2020-06, Vol.16 (3), p.1-31
  • Descrição: We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a d -degenerate graph G and an integer k , outputs an independent set Y , such that for every independent set X in G of size at most k , the probability that X is a subset of Y is at least (( (d+1)k k ) . k (d+1)) -1 . The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph G , a set T = {s_1, t_1} , {s_2, t_2}, ... , {s_ℓ , t_ℓ} of terminal pairs, and an integer k , returns an induced subgraph G* of G that maintains all the inclusion minimal multicuts of G of size at most k and does not contain any ( k +2)-vertex connected set of size 2 O(k) . In particular, G* excludes a clique of size 2 O(k) as a topological minor. Put together, our new tools yield new randomized fixed parameter tractable (FPT) algorithms for S TABLE s-t S EPARATOR , S TABLE O DD C YCLE T RANSVERSAL , and S TABLE M ULTICUT on general graphs, and for S TABLE D IRECTED F EEDBACK V ERTEX S ET on d -degenerate graphs, resolving two problems left open by Marx et al. [ ACM Transactions on Algorithms, 2013{. All of our algorithms can be derandomized at the cost of a small overhead in the running time.
  • Editor: ACM
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.