Propagation via Kernelization: The Vertex Cover Constraint
The technique of kernelization consists in extracting, from an instance of a problem, an essentially equivalent instance whose size is bounded in a parameter k. Besides being the basis for efficient param-eterized algorithms, this method also provides a wealth of information to reason about in the context of constraint programming. We study the use of kernelization for designing propagators through the example of the Vertex Cover constraint. Since the classic kernelization rules often correspond to dominance rather than consistency, we introduce the notion of "loss-less" kernel. While our preliminary experimental results show the potential of the approach, they also show some of its limits. In particular, this method is more effective for vertex covers of large and sparse graphs, as they tend to have, relatively, smaller kernels.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
What is known about Vertex Cover Kernelization?
We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkovi\v{c} on the occasion of his 60th birthday. The Vertex Cover problem is often referred to as the Drosophila …
SurveySolving the undirected feedback vertex set problem by local search
An undirected graph consists of a set of vertices and a set of undirected edges between vertices. Such a graph may contain an abundant number of cycles, then a feedback vertex set (FVS) is a set of vertices intersecting …
Feedback Vertex Set (FVS)Graph Clustering with Cross-View Feature Propagation
Graph clustering is a fundamental and challenging learning task, which is conventionally approached by grouping similar vertices based on edge structure and feature similarity.In contrast to previous methods, in this pap…
ClusteringGraph ClusteringEfficient inference in stochastic block models with vertex labels
We study the stochastic block model with two communities where vertices contain side information in the form of a vertex label. These vertex labels may have arbitrary label distributions, depending on the community membe…
Stochastic Block ModelDenseHMM: Learning Hidden Markov Models by Learning Dense Representations
We propose DenseHMM - a modification of Hidden Markov Models (HMMs) that allows to learn dense representations of both the hidden states and the observables. Compared to the standard HMM, transition probabilities are not…