×

Solving multicut faster than \(2^{n }\). (English) Zbl 1425.05154

Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8737, 666-676 (2014).
Summary: In the Multicut problem, we are given an undirected graph \(G = (V,E)\) and a family \(\mathcal{T} = \{({s_i}{t_i}) \mid s_i, t_i \in V\}\) of pairs of requests and the objective is to find a minimum sized set \(S \subseteq V\) such that every connected component of \(G \setminus S\) contains at most one of \(s _{i }\) and \(t _{i }\) for any pair \(({s_i}{t_i})\in \mathcal{T}\). In this paper we give the first non-trivial algorithm for Multicut running in time \(\mathcal{O}(1.987^n)\).
For the entire collection see [Zbl 1295.68031].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI