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

Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts

Ramanujan, M ; Saurabh, Saket

ACM transactions on algorithms, 2017-12, Vol.13 (4), p.1-25 [Periódico revisado por pares]

ACM

Texto completo disponível

Citações Citado por
  • Título:
    Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
  • Autor: Ramanujan, M ; Saurabh, Saket
  • Assuntos: backdoors to satisfiability ; Graph bipartization ; graph separation problems
  • É parte de: ACM transactions on algorithms, 2017-12, Vol.13 (4), p.1-25
  • Descrição: A skew-symmetric graph ( D =( V , A ),σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on skew-symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte and later by Goldberg and Karzanov. In this article, we introduce a separation problem, d -S kew -S ymmetric M ulticut , where we are given a skew-symmetric graph D , a family τ of d -size subsets of vertices, and an integer k . The objective is to decide whether there is a set X A of k arcs such that every set J in the family has a vertex such that and σ( ) are in different strongly connected components of D ′=( V ,A \ ( X ∪ σ( X )). In this work, we give an algorithm for d -S kew -S ymmetric M ulticut that runs in time O ((4 d ) k ( m + n + )), where m is the number of arcs in the graph, n is the number of vertices, and is the length of the family given in the input. This problem, apart from being independently interesting, also captures the main combinatorial difficulty of numerous classical problems. Our algorithm for d -S kew -S ymmetric M ulticut paves the way for the first linear-time parameterized algorithms for several problems. We demonstrate its utility by obtaining the following linear-time parameterized algorithms: - We show that A lmost 2-SAT is a special case of 1-S kew -S ymmetric M ulticut , resulting in an algorithm for A lmost 2-SAT that runs in time O (4 k k 4 ), where k is the size of the solution and is the length of the input formula. Then, using linear-time parameter-preserving reductions to A lmost 2-SAT, we obtain algorithms for O dd C ycle T ransversal and E dge B ipartization that run in time O (4 k k 4 ( m + n )) and O (4 k k 5 ( m + n )), respectively, where k is the size of the solution, and m and n are the number of edges and vertices respectively. This resolves an open problem posed by Reed et al. and improves on the earlier almost-linear-time algorithm of Kawarabayashi and Reed. - We show that D eletion q-Horn B ackdoor S et D etection is a special case of 3-S kew -S ymmetric M ulticut , giving us an algorithm for D eletion q-Horn B ackdoor S et D etection that runs in time O (12 k k 5 ), where k is the size of the solution and is the length of the input formula. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a work by Narayanaswamy et al. Using this result, we get an algorithm for S atisfiability that runs in time O (12 k k 5 ), where k is the size of the smallest q-Horn deletion backdoor set, with being the length of the input formula.
  • 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.