Clustering with Local Restrictions

DOI10.1007/978-3-642-22006-7_66MaRDI QIDQ3012850zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, Dániel Marx

Publication date 6 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.03885

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Abstract: We study a family of graph clustering problems where each cluster has to satisfy a certain local requirement. Formally, let $mu$ be a function on the subsets of vertices of a graph $G$. In the $(mu,p,q)$-PARTITION problem, the task is to find a partition of the vertices into clusters where each cluster $C$ satisfies the requirements that (1) at most $q$ edges leave $C$ and (2) $mu(C)lep$. Our first result shows that if $mu$ is an {em arbitrary} polynomial-time computable monotone function, then $(mu,p,q)$-PARTITION can be solved in time $n^{O(q)}$, i.e., it is polynomial-time solvable {em for every fixed $q$}. We study in detail three concrete functions $mu$ (the number of vertices in the cluster, number of nonedges in the cluster, maximum number of non-neighbors a vertex has in the cluster), which correspond to natural clustering problems. For these functions, we show that $(mu,p,q)$-PARTITION can be solved in time $2^{O(p)}cdot{n}^{O(1)}$ and in time $2^{O(q)}cdot{n}^{O(1)}$ on $n$-vertex graphs, i.e., the problem is fixed-parameter tractable parameterized by $p$ or by $q$.

Recommendations

• Clustering with local restrictions
• Clustering with center constraints
• Clustering with relational constraint
• Constrained clustering with a complex cluster structure
• Local algorithms for interactive clustering

Cites work

• A fixed-parameter algorithm for the directed feedback vertex set problem
• Aggregating inconsistent information
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• Clustering with local restrictions
• Color-coding
• Correlation clustering
• Correlation clustering with noisy input
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Generalized graph clustering: recognizing (p,q)-cluster graphs
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• Introduction to algorithms
• On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
• Online correlation clustering
• Parameterized graph separation problems

Cited in

(7)

• Clustering with local restrictions
• Clique partitioning with value-monotone submodular cost
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
• Generalized graph clustering: recognizing (p,q)-cluster graphs
• Important separators and parameterized algorithms
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset

This page was built for publication: Clustering with Local Restrictions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012850)