Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Clique Cover and Graph Separation
View through CrossRef
The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this article, we show that, unless the polynomial hierarchy collapses to its third level, the following parameterized problems do not admit a polynomial-time preprocessing algorithm that reduces the size of an instance to polynomial in the parameter:
---Edge Clique Cover, parameterized by the number of cliques, ---Directed Edge/Vertex Multiway Cut, parameterized by the size of the cutset, even in the case of two terminals, ---Edge/Vertex Multicut, parameterized by the size of the cutset, and ---
k
-Way Cut, parameterized by the size of the cutset.
Association for Computing Machinery (ACM)
Title: Clique Cover and Graph Separation
Description:
The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity.
In this article, we show that, unless the polynomial hierarchy collapses to its third level, the following parameterized problems do not admit a polynomial-time preprocessing algorithm that reduces the size of an instance to polynomial in the parameter:
---Edge Clique Cover, parameterized by the number of cliques, ---Directed Edge/Vertex Multiway Cut, parameterized by the size of the cutset, even in the case of two terminals, ---Edge/Vertex Multicut, parameterized by the size of the cutset, and ---
k
-Way Cut, parameterized by the size of the cutset.
Related Results
Sobre grafos clique críticos
Sobre grafos clique críticos
Se llama completo de un grafo a un conjunto de vértices adyacentes entre si; si un completo es maximal con respecto a la inclusión, se dice que es un clique del grafo. Los cliques ...
Rank-sparsity decomposition for planted quasi clique recovery
Rank-sparsity decomposition for planted quasi clique recovery
Abstract
In this paper, we apply the Rank-Sparsity Matrix Decomposition to the planted Maximum Quasi-Clique Problem (MQCP). This problem has ...
Tropical Graph Parameters
Tropical Graph Parameters
Connection matrices for graph parameters with values in a field have been introduced by M. Freedman, L. Lovász and A. Schrijver (2007). Graph parameters with connection matrices o...
Graph convolutional neural networks for 3D data analysis
Graph convolutional neural networks for 3D data analysis
(English) Deep Learning allows the extraction of complex features directly from raw input data, eliminating the need for hand-crafted features from the classical Machine Learning p...
Graph data warehousing
Graph data warehousing
Over the last decade, we have witnessed the emergence of networks in a wide spectrum of application domains, ranging from social and information networks to biological and transpor...
CliReg: Clique-based robust Point Cloud Registration
CliReg: Clique-based robust Point Cloud Registration
We propose a branch-and-bound algorithm for robust rigid registration of two point clouds in the presence of a large number of outlier correspondences. For this purpose, we conside...
Bilangan Terhubung Titik Pelangi pada Graf Garis dan Graf Tengah dari Hasil Operasi Comb Graf Bintang C<sub>3</sub> dan Graf Bintang S<sub>n</sub>
Bilangan Terhubung Titik Pelangi pada Graf Garis dan Graf Tengah dari Hasil Operasi Comb Graf Bintang C<sub>3</sub> dan Graf Bintang S<sub>n</sub>
Penelitian ini bertujuan menentukan bilangan terhubung titik pelangi (rainbow vertex connection number) pada graf garis dan graf tengah yang diperoleh dari hasil operasi comb antar...
How Many Cliques Can a Clique Cover Cover?
How Many Cliques Can a Clique Cover Cover?
This work examines the problem of clique enumeration on a graph by exploiting its clique covers. The principle of inclusion/exclusion is applied to determine the number of cliques ...