Lokshtanov, Daniel; Saurabh, Saket; Suchý, Ondřej 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]. Cited in 1 Document 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 \textit{D. Lokshtanov} et al., Lect. Notes Comput. Sci. 8737, 666--676 (2014; Zbl 1425.05154) Full Text: DOI