FixCon: A Generic Solver for Fixed-Cardinality Subgraph Problems
FixCon: A Generic Solver for Fixed-Cardinality Subgraph Problems
复制标题
DOI：
10.1137/1.9781611976007.2
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Christian Komusiewicz;Frank Sommer
中科院分区：
文献类型：
--
作者：
Christian Komusiewicz;Frank Sommer
在图中的固定基数优化问题中，我们给定一个图G =（V，E），一个目标函数f和一个整数k，并搜索一个k个顶点的集合S V，使f（G [ S ]）最大化，其中G [ S ]是由S诱导的G的子图。当G [ S ]需要连接时，我们实现了一个基于枚举的算法来解决固定基数优化问题。为了避免枚举所有连通子图的顺序k，我们提出了几个通用的修剪规则和一个通用的启发式计算目标值的下限。我们进行了实验分析的算法的性能和有用的8个例子的问题，其中一个的目的是找到密集，稀疏，或度约束连接的子图，分别剪枝规则。我们的实验表明，当这个通用的求解器与特定于问题的修剪规则相结合时，我们的算法与这些问题的开箱即用的ILP公式具有竞争力。
In fixed-cardinality optimization problems in graphs, we are given a graph G = ( V, E ), an objective function f , and an integer k and search for a set S ⊆ V of k vertices that maximizes f ( G [ S ]) where G [ S ] is the subgraph of G induced by S . We implement an enumeration-based algorithm for solving fixed-cardinality optimization problems when G [ S ] needs to be connected. To avoid enumerating all connected subgraphs of order k , we present several generic pruning rules and a generic heuristic for computing a lower bound for the objective value. We perform an experimental analysis of the performance of the algorithm and the usefulness of the pruning rules for eight example problems in which one aims to find dense, sparse, or degree-constrained connected subgraphs, respectively. Our experiments show that, when this generic solver is combined with problem-specific pruning rules, our algorithm is competitive with out-of-the-box ILP formulations for these problems.