Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Parameterized Algorithms for Graph Partitioning Problems
verfasst von : Hadas Shachnai, Meirav Zehavi
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We study a broad class of graph partitioning problems, where each problem is specified by a graph \(G=(V,E)\), and parameters \(k\) and \(p\). We seek a subset \(U\subseteq V\) of size \(k\), such that \(\alpha _1m_1 + \alpha _2m_2\) is at most (or at least) \(p\), where \(\alpha _1,\alpha _2\in \mathbb {R}\) are constants defining the problem, and \(m_1, m_2\) are the cardinalities of the edge sets having both endpoints, and exactly one endpoint, in \(U\), respectively. This class of fixed-cardinality graph partitioning problems (FGPPs) encompasses Max
\((k,n-k)\)-Cut, Min
\(k\)-Vertex Cover, \(k\)-Densest Subgraph, and \(k\)-Sparsest Subgraph.
Our main result is an \(O^*(4^{k+o(k)}\varDelta ^k)\) algorithm for any problem in this class, where \(\varDelta \ge 1\) is the maximum degree in the input graph. This resolves an open question posed by Bonnet et al. [IPEC 2013]. We obtain faster algorithms for certain subclasses of FGPPs, parameterized by \(p\), or by \((k+p)\). In particular, we give an \(O^*(4^{p+o(p)})\) time algorithm for Max
\((k,n-k)\)-Cut, thus improving significantly the best known \(O^*(p^p)\) time algorithm.