To see the other types of publications on this topic, follow the link: K-clique problem.
Journal articles on the topic 'K-clique problem'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'K-clique problem.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Wu, Jun, and Minghao Yin. "A Restart Local Search for Solving Diversified Top-k Weight Clique Search Problem." Mathematics 9, no. 21 (October 21, 2021): 2674. http://dx.doi.org/10.3390/math9212674.
Full textAbstract:
Diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with practical applications. The diversified top-k weight clique search problem aims to search k maximal cliques that can cover the maximum weight in a vertex weighted graph. In this work, we propose a novel local search algorithm called TOPKWCLQ for the DTKWC search problem which mainly includes two strategies. First, a restart strategy is adopted, which repeated the construction and updating processes of the maximal weight clique set. Second, a scoring heuristic is designed by giving different priorities for maximal weight cliques in candidate set. Meanwhile, a constraint model of the DTKWC search problem is constructed such that the research concerns can be evaluated. Experimental results show that the proposed algorithm TOPKWCLQ outperforms than the comparison algorithm on large-scale real-world graphs.
2
Lee, Chuan-Min. "Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs." Algorithms 14, no. 1 (January 13, 2021): 22. http://dx.doi.org/10.3390/a14010022.
Full textAbstract:
This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {k}-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the {k}-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the {k}-clique transversal problem is polynomial-time solvable for graphs whose clique transversal numbers equal their clique independence numbers. We also show the relationship between the signed and generalization clique problems and present NP-completeness results for the considered problems on k-trees with unbounded k, planar graphs, doubly chordal graphs, total graphs, split graphs, line graphs, and dually chordal graphs.
3
Sanei-Mehri, Seyed-Vahid, Apurba Das, Hooman Hashemi, and Srikanta Tirthapura. "Mining Largest Maximal Quasi-Cliques." ACM Transactions on Knowledge Discovery from Data 15, no. 5 (June 26, 2021): 1–21. http://dx.doi.org/10.1145/3446637.
Full textAbstract:
Quasi-cliques are dense incomplete subgraphs of a graph that generalize the notion of cliques. Enumerating quasi-cliques from a graph is a robust way to detect densely connected structures with applications in bioinformatics and social network analysis. However, enumerating quasi-cliques in a graph is a challenging problem, even harder than the problem of enumerating cliques. We consider the enumeration of top- k degree-based quasi-cliques and make the following contributions: (1) we show that even the problem of detecting whether a given quasi-clique is maximal (i.e., not contained within another quasi-clique) is NP-hard. (2) We present a novel heuristic algorithm K ernel QC to enumerate the k largest quasi-cliques in a graph. Our method is based on identifying kernels of extremely dense subgraphs within a graph, followed by growing subgraphs around these kernels, to arrive at quasi-cliques with the required densities. (3) Experimental results show that our algorithm accurately enumerates quasi-cliques from a graph, is much faster than current state-of-the-art methods for quasi-clique enumeration (often more than three orders of magnitude faster), and can scale to larger graphs than current methods.
4
Sun, Bintao, Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. "KClist++." Proceedings of the VLDB Endowment 13, no. 10 (June 2020): 1628–40. http://dx.doi.org/10.14778/3401960.3401962.
Full textAbstract:
The problem of finding densest subgraphs has received increasing attention in recent years finding applications in biology, finance, as well as social network analysis. The k -clique densest subgraph problem is a generalization of the densest subgraph problem, where the objective is to find a subgraph maximizing the ratio between the number of k -cliques in the subgraph and its number of nodes. It includes as a special case the problem of finding subgraphs with largest average number of triangles ( k = 3), which plays an important role in social network analysis. Moreover, algorithms that deal with larger values of k can effectively find quasi-cliques. The densest subgraph problem can be solved in polynomial time with algorithms based on maximum flow, linear programming or a recent approach based on convex optimization. In particular, the latter approach can scale to graphs containing tens of billions of edges. While finding a densest subgraph in large graphs is no longer a bottleneck, the k -clique densest subgraph remains challenging even when k = 3. Our work aims at developing near-optimal and exact algorithms for the k -clique densest subgraph problem on large real-world graphs. We give a surprisingly simple procedure that can be employed to find the maximal k -clique densest subgraph in large-real world graphs. By leveraging appealing properties of existing results, we combine it with a recent approach for listing all k -cliques in a graph and a sampling scheme, obtaining the state-of-the-art approaches for the aforementioned problem. Our theoretical results are complemented with an extensive experimental evaluation showing the effectiveness of our approach in large real-world graphs.
5
Szabó, Sándor, and Bogdán Zaválnij. "Clique Search in Graphs of Special Class and Job Shop Scheduling." Mathematics 10, no. 5 (February 23, 2022): 697. http://dx.doi.org/10.3390/math10050697.
Full textAbstract:
In this paper, we single out the following particular case of the clique search problem. The vertices of the given graph are legally colored with k colors and we are looking for a clique with k nodes in the graph. In other words, we want to decide if a given k-partite graph contains a clique with k nodes. The maximum clique problem asks for finding a maximum clique in a given finite simple graph. The problem of deciding if the given graph contains a clique with k vertices is called the k-clique problem. The first problem is NP-hard and the second one is NP-complete. The special clique search problem, we propose, is still an NP-complete problem. We will show that the k-clique problem in the special case of k-partite graphs is more tractable than in the general case. In order to illustrate the possible practical utility of this restricted type clique search problem we will show that the job shop scheduling problem can be reduced to such a clique search problem in a suitable constructed graph. We carry out numerical experiments to assess the efficiency of the approach. It is a common practice that before one embarks on a large scale clique search typically one attempts to simplify and tidy up the given graph. This procedure is commonly referred as preconditioning or kernelization of the given graph. Of course, the preconditioning or kernelization is meant with respect to the given type of clique search problem. The other main topic of the paper is to describe a number of kernelization methods tailored particularly to the proposed special k-clique problem. Some of these techniques works in connection with the generic k-clique problem. In these situations, we will see that they are more efficient in the case of k-partite graphs. Some other preconditioning methods applicable only to k-partite graphs. We illustrate how expedient these preconditioning methods can be by solving non-trivial scheduling problems to optimality employing only kernelization techniques dispensing with exhaustive clique search algorithms altogether.
6
Wu, Jun, and Minghao Yin. "A Hybrid Evolutionary Algorithm for the Diversified Top-k Weight Clique Search Problem (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 11 (June 28, 2022): 13083–84. http://dx.doi.org/10.1609/aaai.v36i11.21678.
Full textAbstract:
The diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique search problem, which extends the DTKC search problem by taking into account the weight of vertices. This problem involves finding at most k maximal weighted cliques that cover maximum weight of vertices with low overlapping in a given graph. In this study, a mixed integer linear program constraint formulation is proposed to model DTKWC search problem and an efficient hybrid evolutionary algorithm (HEA-D) based on some heuristic strategies is proposed to tackle it. Experiments on two sets of 110 graphs show that HEA-D outperforms the state-of-art methods.
7
Conte, Alessio, Donatella Firmani, Maurizio Patrignani, and Riccardo Torlone. "A meta-algorithm for finding large k-plexes." Knowledge and Information Systems 63, no. 7 (May 1, 2021): 1745–69. http://dx.doi.org/10.1007/s10115-021-01570-8.
Full textAbstract:
AbstractWe focus on the automatic detection of communities in large networks, a challenging problem in many disciplines (such as sociology, biology, and computer science). Humans tend to associate to form families, villages, and nations. Similarly, the elements of real-world networks naturally tend to form highly connected groups. A popular model to represent such structures is the clique, that is, a set of fully interconnected nodes. However, it has been observed that cliques are too strict to represent communities in practice. The k-plex relaxes the notion of clique, by allowing each node to miss up to k connections. Although k-plexes are more flexible than cliques, finding them is more challenging as their number is greater. In addition, most of them are small and not significant. In this paper we tackle the problem of finding only large k-plexes (i.e., comparable in size to the largest clique) and design a meta-algorithm that can be used on top of known enumeration algorithms to return only significant k-plexes in a fraction of the time. Our approach relies on: (1) methods for strongly reducing the search space and (2) decomposition techniques based on the efficient computation of maximal cliques. We demonstrate experimentally that known enumeration algorithms equipped with our approach can run orders of magnitude faster than full enumeration.
8
DEKEL, YAEL, ORI GUREL-GUREVICH, and YUVAL PERES. "Finding Hidden Cliques in Linear Time with High Probability." Combinatorics, Probability and Computing 23, no. 1 (November 14, 2013): 29–49. http://dx.doi.org/10.1017/s096354831300045x.
Full textAbstract:
We are given a graph G with n vertices, where a random subset of k vertices has been made into a clique, and the remaining edges are chosen independently with probability $\frac12$. This random graph model is denoted $G(n,\frac12,k)$. The hidden clique problem is to design an algorithm that finds the k-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov [3] uses spectral techniques to find the hidden clique with high probability when $k = c \sqrt{n}$ for a sufficiently large constant c > 0. Recently, an algorithm that solves the same problem was proposed by Feige and Ron [12]. It has the advantages of being simpler and more intuitive, and of an improved running time of O(n2). However, the analysis in [12] gives a success probability of only 2/3. In this paper we present a new algorithm for finding hidden cliques that both runs in time O(n2) (that is, linear in the size of the input) and has a failure probability that tends to 0 as n tends to ∞. We develop this algorithm in the more general setting where the clique is replaced by a dense random graph.
9
McCreesh, Ciaran, and Patrick Prosser. "Finding Maximum k-Cliques Faster Using Lazy Global Domination." Proceedings of the International Symposium on Combinatorial Search 7, no. 1 (September 1, 2021): 72–80. http://dx.doi.org/10.1609/socs.v7i1.18387.
Full textAbstract:
A clique in a graph is a set of vertices, each of which is adjacent to every other vertex in this set. A k-clique relaxes this requirement, requiring vertices to be within a distance k of each other, rather than directly adjacent. In theory, a maximum clique algorithm can easily be adapted to solve the maximum k-clique problem, although large sparse k-clique graphs reduce to large dense clique graphs, which can be computationally challenging. We adapt a state of the art maximum clique algorithm to show that this reduction is in fact useful in practice, and introduce a lazy global domination rule which sometimes vastly reduces the search space. We include experimental results for a range of real-world and benchmark graphs, and a detailed look at random graphs. We also use thread-parallel search to solve some harder instances.
10
Goldschmidt, Oliver, Dorit S. Hochbaum, Cor Hurkens, and Gang Yu. "Approximation Algorithms for the k-Clique Covering Problem." SIAM Journal on Discrete Mathematics 9, no. 3 (August 1996): 492–509. http://dx.doi.org/10.1137/s089548019325232x.
Full text
11
Liazi, Maria, Ioannis Milis, Fanny Pascual, and Vassilis Zissimopoulos. "The densest k-subgraph problem on clique graphs." Journal of Combinatorial Optimization 14, no. 4 (March 21, 2007): 465–74. http://dx.doi.org/10.1007/s10878-007-9069-1.
Full text
12
Suyudi, Mochamad, Asep K. Supriatna, and Sukono Sukono. "Alternative Branching Strategies in the Branch and Bound Algorithm by Using a k-clique covering vertex set for Maximum Clique Problems." International Journal of Quantitative Research and Modeling 1, no. 4 (December 5, 2020): 208–16. http://dx.doi.org/10.46336/ijqrm.v1i4.82.
Full textAbstract:
The Maximum clique problem (MCP) is graph theory problem that demand complete subgraf with maximum cardinality (maximum clique) in arbitrary graph. Solving MCP usually use Branch and Bound (BnB) algorithm, in this paper we will show how n + 1 color classes (where n is the difference between upper and lower bound) selected to form k-clique covering vertex set which later used for branching strategy can guarenteed finnding maximum clique.
13
Suyudi, Mochamad, Asep K. Supriatna, and Sukono Sukono. "Alternative Branching Strategies in the Branch and Bound Algorithm by Using a k-clique covering vertex set for Maximum Clique Problems." International Journal of Quantitative Research and Modeling 1, no. 4 (December 5, 2020): 208–16. http://dx.doi.org/10.46336/ijqrm.v1i4.82.
Full textAbstract:
The Maximum clique problem (MCP) is graph theory problem that demand complete subgraf with maximum cardinality (maximum clique) in arbitrary graph. Solving MCP usually use Branch and Bound (BnB) algorithm, in this paper we will show how n + 1 color classes (where n is the difference between upper and lower bound) selected to form k-clique covering vertex set which later used for branching strategy can guarenteed finnding maximum clique.
14
Suyudi, Mochamad, Asep K. Supriatna, and Sukono Sukono. "Alternative Branching Strategies in the Branch and Bound Algorithm by Using a K-Clique Covering Vertex Set for Maximum Clique Problems." International Journal of Quantitative Research and Modeling 1, no. 4 (December 2, 2020): 208–16. http://dx.doi.org/10.46336/ijqrm.v1i4.92.
Full textAbstract:
The maximum clique problem (MCP) is graph theory problem that demand complete subgraph with maximum cardinality (maximum clique) in arbitrary graph. Solving MCP usually use Branch and Bound (BnB) algorithm. In this paper, we will show how n + 1 color classes (where n is the difference between upper and lower bound) selected to form k-clique covering vertex set which later used for branching strategy can guarantee finding maximum clique.
15
Malod-Dognin, Noël, Rumen Andonov, and Nicola Yanev. "Solving Maximum Clique Problem for Protein Structure Similarity." Serdica Journal of Computing 4, no. 1 (March 31, 2010): 93–100. http://dx.doi.org/10.55630/sjc.2010.4.93-100.
Full textAbstract:
Computing the similarity between two protein structures is a crucial task in molecular biology, and has been extensively investigated. Many protein structure comparison methods can be modeled as maximum weighted clique problems in specific k-partite graphs, referred here as alignment graphs. In this paper we present both a new integer programming formulation for solving such clique problems and a dedicated branch and bound algorithm for solving the maximum cardinality clique problem. Both approaches have been integrated in VAST, a software for aligning protein 3D structures largely used in the National Center for Biotechnology Information, an original clique solver which uses the well known Bron and Kerbosch algorithm (BK). Our computational results on real protein alignment instances show that our branch and bound algorithm is up to 116 times faster than BK.
16
Stern, Roni, Meir Kalech, and Ariel Felner. "Searching for a k-Clique in Unknown Graphs." Proceedings of the International Symposium on Combinatorial Search 1, no. 1 (August 25, 2010): 83–89. http://dx.doi.org/10.1609/socs.v1i1.18175.
Full textAbstract:
Agents that solve problems in unknown graphs are usually required to iteratively explore parts of the graph. In this paper we research the problem of finding a k-clique in an unknown graph while minimizing the number of required exploration actions. Two novel heuristics Known Degree and Clique* are proposed to reduce the required exploration cost by carefully choosing which part of the environment to explore. We further investigate the problem by adding probabilistic knowledge of the graph and propose an Markov Decision Process(MDP) and a Monte Carlo based heuristic (RClique*) that uses knowledge of edge probabilities to reduce the required exploration cost. We demonstrate the efficiency of the proposed approaches on simulated random and scale free graphs as well as on real online web crawls.
17
Koh, Yeong Jun, Yuk Heo, and Chang-Su Kim. "Sequential Clique Optimization for Unsupervised and Weakly Supervised Video Object Segmentation." Electronics 11, no. 18 (September 13, 2022): 2899. http://dx.doi.org/10.3390/electronics11182899.
Full textAbstract:
A novel video object segmentation algorithm, which segments out multiple objects in a video sequence in unsupervised or weakly supervised manners, is proposed in this work. First, we match visually important object instances to construct salient object tracks through a video sequence without any user supervision. We formulate this matching process as the problem to find maximal weight cliques in a complete k-partite graph and develop the sequential clique optimization algorithm to determine the cliques efficiently. Then, we convert the resultant salient object tracks into object segmentation results and refine them based on Markov random field optimization. Second, we adapt the sequential clique optimization algorithm to perform weakly supervised video object segmentation. To this end, we develop a sparse-to-dense network to convert the point cliques into segmentation results. The experimental results demonstrate that the proposed algorithm provides comparable or better performances than recent state-of-the-art VOS algorithms.
18
Ames, Brendan P. W., and Stephen A. Vavasis. "Convex optimization for the planted k-disjoint-clique problem." Mathematical Programming 143, no. 1-2 (December 7, 2013): 299–337. http://dx.doi.org/10.1007/s10107-013-0733-1.
Full text
19
Wu, Jun, Chu-Min Li, Lu Jiang, Junping Zhou, and Minghao Yin. "Local search for diversified Top-k clique search problem." Computers & Operations Research 116 (April 2020): 104867. http://dx.doi.org/10.1016/j.cor.2019.104867.
Full text
20
Zhou, Yi, Jingwei Xu, Zhenyu Guo, Mingyu Xiao, and Yan Jin. "Enumerating Maximal k-Plexes with Worst-Case Time Guarantee." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 03 (April 3, 2020): 2442–49. http://dx.doi.org/10.1609/aaai.v34i03.5625.
Full textAbstract:
The problem of enumerating all maximal cliques in a graph is a key primitive in a variety of real-world applications such as community detection and so on. However, in practice, communities are rarely formed as cliques due to data noise. Hence, k-plex, a subgraph in which any vertex is adjacent to all but at most k vertices, is introduced as a relaxation of clique. In this paper, we investigate the problem of enumerating all maximal k-plexes and present FaPlexen, an enumeration algorithm which integrates the “pivot” heuristic and new branching schemes. To our best knowledge, for the first time, FaPlexen lists all maximal k-plexes with provably worst-case running time O(n2γn) in a graph with n vertices, where γ < 2. Then, we propose another algorithm CommuPlex which non-trivially extends FaPlexen to find all maximal k-plexes of prescribed size for community detection in massive real-life networks. We finally carry out experiments on both real and synthetic graphs and demonstrate that our algorithms run much faster than the state-of-the-art algorithms.
21
Gupta, Anupam, David G. Harris, Euiwoong Lee, and Jason Li. "Optimal Bounds for the k -cut Problem." Journal of the ACM 69, no. 1 (February 28, 2022): 1–18. http://dx.doi.org/10.1145/3478018.
Full textAbstract:
In the k -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into k connected components. Algorithms of Karger and Stein can solve this in roughly O ( n 2k ) time. However, lower bounds from conjectures about the k -clique problem imply that Ω ( n (1- o (1)) k ) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for general k -cut in n 1.98k + O(1) time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights). In this work, we resolve the problem for general graphs. We show that the Contraction Algorithm of Karger outputs any fixed k -cut of weight α λ k with probability Ω k ( n - α k ), where λ k denotes the minimum k -cut weight. This also gives an extremal bound of O k ( n k ) on the number of minimum k -cuts and an algorithm to compute λ k with roughly n k polylog( n ) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weight k -clique. The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 λ k / k , using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—in the Karger process.
22
Teixeira, Rafael B., and Celina M. Herrera de Figueiredo. "The sandwich problem for cutsets: Clique cutset, k-star cutset." Discrete Applied Mathematics 154, no. 13 (August 2006): 1791–98. http://dx.doi.org/10.1016/j.dam.2006.03.023.
Full text
23
YANG, GANG, ZHENG TANG, ZHIQIANG ZHANG, and YUNYI ZHU. "A FLEXIBLE ANNEALING CHAOTIC NEURAL NETWORK TO MAXIMUM CLIQUE PROBLEM." International Journal of Neural Systems 17, no. 03 (June 2007): 183–92. http://dx.doi.org/10.1142/s0129065707001056.
Full textAbstract:
Based on the analysis and comparison of several annealing strategies, we present a flexible annealing chaotic neural network which has flexible controlling ability and quick convergence rate to optimization problem. The proposed network has rich and adjustable chaotic dynamics at the beginning, and then can converge quickly to stable states. We test the network on the maximum clique problem by some graphs of the DIMACS clique instances, p-random and k random graphs. The simulations show that the flexible annealing chaotic neural network can get satisfactory solutions at very little time and few steps. The comparison between our proposed network and other chaotic neural networks denotes that the proposed network has superior executive efficiency and better ability to get optimal or near-optimal solution.
24
Czumaj, Artur, and Christian Konrad. "Detecting cliques in CONGEST networks." Distributed Computing 33, no. 6 (December 21, 2019): 533–43. http://dx.doi.org/10.1007/s00446-019-00368-w.
Full textAbstract:
AbstractThe problem of detecting network structures plays a central role in distributed computing. One of the fundamental problems studied in this area is to determine whether for a given graph H, the input network contains a subgraph isomorphic to H or not. We investigate this problem for H being a clique $$K_{\ell }$$ K ℓ in the classical distributed model, where the communication topology is the same as the topology of the underlying network, and with limited communication bandwidth on the links. Our first and main result is a lower bound, showing that detecting $$K_{\ell }$$ K ℓ requires $$\varOmega (\sqrt{n} / {\mathfrak {b}})$$ Ω ( n / b ) communication rounds, for every $$4 \le \ell \le \sqrt{n}$$ 4 ≤ ℓ ≤ n , and $$\varOmega (n / (\ell {\mathfrak {b}}))$$ Ω ( n / ( ℓ b ) ) rounds for every $$\ell \ge \sqrt{n}$$ ℓ ≥ n , where $${\mathfrak {b}}$$ b is the bandwidth of the communication links. This result is obtained by using a reduction to the set disjointness problem in the framework of two-party communication complexity. We complement our lower bound with a two-party communication protocol for listing all cliques in the input graph, which up to constant factors communicates the same number of bits as our lower bound for $$K_4$$ K 4 detection. This demonstrates that our lower bound cannot be improved using the two-party communication framework.
25
Liang, Zuosong, Erfang Shan, and Liying Kang. "The clique-transversal set problem in {claw, K 4 }-free planar graphs." Information Processing Letters 118 (February 2017): 64–68. http://dx.doi.org/10.1016/j.ipl.2016.10.001.
Full text
26
Li, Changhong. "Multi-objective Optimization Overlapping Community Detection Algorithm based on Subgraph Structure." Frontiers in Computing and Intelligent Systems 3, no. 3 (May 17, 2023): 110–12. http://dx.doi.org/10.54097/fcis.v3i3.8580.
Full textAbstract:
Community detection in complex networks has increasingly become an important topic in the network, but in most community detection methods, a single node only belongs to one community. In fact, there is often overlap among real-world online communities. In this paper, an overlapping community detection algorithm based on subgraph structure and multi-optimization method is designed. In this algorithm, the maximum clique mined by k-core decomposition is used as the clique node, thus the overlap characteristic is transformed into the inherent characteristic of the new graph. After that, a population initialization method based on k-core decomposition is designed, and the discrete framework of multi-objective particle swarm optimization algorithm is used to optimize the two objectives on the basis of maximal clique graph to solve the problem of overlapping community detection. In the real-world network, this algorithm is compared with similar community detection algorithms. The comparison of the evaluation indexe shows that the community detection effect of this algorithm is similar to that of similar algorithms, and has a good application prospect.
27
Gao, Jian, Zhenghang Xu, Ruizhi Li, and Minghao Yin. "An Exact Algorithm with New Upper Bounds for the Maximum k-Defective Clique Problem in Massive Sparse Graphs." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (June 28, 2022): 10174–83. http://dx.doi.org/10.1609/aaai.v36i9.21257.
Full textAbstract:
The Maximum k-Defective Clique Problem (MDCP), as a clique relaxation model, has been used to solve various problems. Because it is a hard computational task, previous works can hardly solve the MDCP for massive sparse graphs derived from real-world applications. In this work, we propose a novel branch-and-bound algorithm to solve the MDCP based on several new techniques. First, we propose two new upper bounds of the MDCP as well as corresponding reduction rules to remove redundant vertices and edges. The proposed reduction rules are particularly useful for massive graphs. Second, we present another new upper bound by counting missing edges between fixed vertices and an unfixed vertex for cutting branches. We perform extensive computational experiments to evaluate our algorithm. Experimental results show that our reduction rules are very effective for removing redundant vertices and edges so that graphs are reduced greatly. Also, our algorithm can solve benchmark instances efficiently, and it has significantly better performance than state-of-the-art algorithms.
28
Wang, Zhaocai, Zuwen Ji, Lei Li, and Dongmei Huang. "A Parallel Computational Algorithm for Solving the Maximum k-Vertex Weighted Clique Problem." Journal of Computational and Theoretical Nanoscience 12, no. 12 (December 1, 2015): 6002–5. http://dx.doi.org/10.1166/jctn.2015.4749.
Full text
29
PIKHURKO, OLEG, KATHERINE STADEN, and ZELEALEM B. YILMA. "The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques." Mathematical Proceedings of the Cambridge Philosophical Society 163, no. 2 (January 23, 2017): 341–56. http://dx.doi.org/10.1017/s0305004116001031.
Full textAbstract:
AbstractLet k := (k1,. . .,ks) be a sequence of natural numbers. For a graph G, let F(G;k) denote the number of colourings of the edges of G with colours 1,. . .,s such that, for every c ∈ {1,. . .,s}, the edges of colour c contain no clique of order kc. Write F(n;k) to denote the maximum of F(G;k) over all graphs G on n vertices. This problem was first considered by Erdős and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases.We prove that, for every k and n, there is a complete multipartite graph G on n vertices with F(G;k) = F(n;k). Also, for every k we construct a finite optimisation problem whose maximum is equal to the limit of log2F(n;k)/${n\choose 2}$ as n tends to infinity. Our final result is a stability theorem for complete multipartite graphs G, describing the asymptotic structure of such G with F(G;k) = F(n;k) · 2o(n2) in terms of solutions to the optimisation problem.
30
BOUAJJANI, AHMED, and AGATHE MERCERON. "Parametric Verification of a Group Membership Algorithm." Theory and Practice of Logic Programming 6, no. 3 (May 2006): 321–53. http://dx.doi.org/10.1017/s1471068406002663.
Full textAbstract:
We address the problem of verifying clique avoidance in the TTP protocol. TTP allows several stations embedded in a car to communicate. It has many mechanisms to ensure robustness to faults. In particular, it has an algorithm that allows a station to recognize itself as faulty and leave the communication. This algorithm must satisfy the crucial ‘non-clique’ property: it is impossible to have two or more disjoint groups of stations communicating exclusively with stations in their own group. In this paper, we propose an automatic verification method for an arbitrary number of stations $N$ and a given number of faults $k$. We give an abstraction that allows to model the algorithm by means of unbounded (parametric) counter automata. We have checked the non-clique property on this model in the case of one fault, using the ALV tool as well as the LASH tool.
31
Angelini, Patrizio, Peter Eades, Seok-Hee Hong, Karsten Klein, Stephen Kobourov, Giuseppe Liotta, Alfredo Navarra, and Alessandra Tappini. "Graph Planarity by Replacing Cliques with Paths." Algorithms 13, no. 8 (August 13, 2020): 194. http://dx.doi.org/10.3390/a13080194.
Full textAbstract:
This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h-Clique2Path Planarity asks whether it is possible to obtain a planar subgraph of G by removing edges from each clique so that the subgraph induced by each subset is a path. We investigate the complexity of this problem in relation to k-planarity. In particular, we prove that h-Clique2Path Planarity is NP-complete even when h=4 and G is a simple 3-plane graph, while it can be solved in linear time when G is a simple 1-plane graph, for any value of h. Our results contribute to the growing fields of hybrid planarity and of graph drawing beyond planarity.
32
SALEH, SAGVAN ALI, and MHAND HIFI. "A FAST METHOD FOR OPTIMIZING THE K-CLUSTERING BI-CLIQUE COMPLETION PROBLEM IN TELECOMMUNICATION." Journal of The University of Duhok 20, no. 1 (July 20, 2017): 175–83. http://dx.doi.org/10.26682/sjuod.2017.20.1.16.
Full text
33
Chen, Jiejiang, Yiyuan Wang, Shaowei Cai, Minghao Yin, Yupeng Zhou, and Jieyu Wu. "NukCP: An Improved Local Search Algorithm for Maximum k-Club Problem." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (June 28, 2022): 10146–55. http://dx.doi.org/10.1609/aaai.v36i9.21254.
Full textAbstract:
The maximum k-club problem (MkCP) is an important clique relaxation problem with wide applications. Previous MkCP algorithms only work on small-scale instances and are not applicable for large-scale instances. For solving instances with different scales, this paper develops an efficient local search algorithm named NukCP for the MkCP which mainly includes two novel ideas. First, we propose a dynamic reduction strategy, which makes a good balance between the time efficiency and the precision effectiveness of the upper bound calculation. Second, a stratified threshold configuration checking strategy is designed by giving different priorities for the neighborhood in the different levels. Experiments on a broad range of different scale instances show that NukCP significantly outperforms the state-of-the-art MkCP algorithms on most instances.
34
Lai, Wenxing. "The Inapproximability of k-DominatingSet for Parameterized AC 0 Circuits †." Algorithms 12, no. 11 (November 4, 2019): 230. http://dx.doi.org/10.3390/a12110230.
Full textAbstract:
Chen and Flum showed that any FPT-approximation of the k-Clique problem is not in para- AC 0 and the k-DominatingSet (k-DomSet) problem could not be computed by para- AC 0 circuits. It is natural to ask whether the f ( k ) -approximation of the k-DomSet problem is in para- AC 0 for some computable function f. Very recently it was proved that assuming W [ 1 ] ≠ FPT , the k-DomSet problem cannot be f ( k ) -approximated by FPT algorithms for any computable function f by S., Laekhanukit and Manurangsi and Lin, seperately. We observe that the constructions used in Lin’s work can be carried out using constant-depth circuits, and thus we prove that para- AC 0 circuits could not approximate this problem with ratio f ( k ) for any computable function f. Moreover, under the hypothesis that the 3-CNF-SAT problem cannot be computed by constant-depth circuits of size 2 ε n for some ε > 0 , we show that constant-depth circuits of size n o ( k ) cannot distinguish graphs whose dominating numbers are either ≤k or > log n 3 log log n 1 / k . However, we find that the hypothesis may be hard to settle by showing that it implies NP ⊈ NC 1 .
35
Wu, Kuixian, Jian Gao, Rong Chen, and Xianji Cui. "Vertex Selection Heuristics in Branch-and-Bound Algorithms for the Maximum k-Plex Problem." International Journal on Artificial Intelligence Tools 28, no. 05 (August 2019): 1950015. http://dx.doi.org/10.1142/s0218213019500155.
Full textAbstract:
As a relaxation of clique in graph theory, k-plex is a powerful tool for analyzing social networks and identifying cohesive structures in graphs. Recently, more and more researchers have concentrated on the algorithms for the maximum k-plex problem. Among those algorithms, a branch-and-bound algorithm proposed very recently shows a good performance on solving large sparse graphs, but does not work well on social networks. In this paper, we propose two novel vertex selection heuristic strategies for branching. The first one employs historical information of vertex reduction, and the second one is a combination of the first heuristic and the degree-based approach. Intensive experiments on Facebook benchmark show that the algorithm combining our heuristics outperforms the state-of-the-art algorithms.
36
Fang, Zhiwen, Chu-Min Li, and Ke Xu. "An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem." Journal of Artificial Intelligence Research 55 (March 31, 2016): 799–833. http://dx.doi.org/10.1613/jair.4953.
Full textAbstract:
Recently, MaxSAT reasoning is shown very effective in computing a tight upper bound for a Maximum Clique (MC) of a (unweighted) graph. In this paper, we apply MaxSAT reasoning to compute a tight upper bound for a Maximum Weight Clique (MWC) of a wighted graph. We first study three usual encodings of MWC into weighted partial MaxSAT dealing with hard clauses, which must be satisfied in all solutions, and soft clauses, which are weighted and can be falsified. The drawbacks of these encodings motivate us to propose an encoding of MWC into a special weighted partial MaxSAT formalism, called LW (Literal-Weighted) encoding and dedicated for upper bounding an MWC, in which both soft clauses and literals in soft clauses are weighted. An optimal solution of the LW MaxSAT instance gives an upper bound for an MWC, instead of an optimal solution for MWC. We then introduce two notions called the Top-k literal failed clause and the Top-k empty clause to extend classical MaxSAT reasoning techniques, as well as two sound transformation rules to transform an LW MaxSAT instance. Successive transformations of an LW MaxSAT instance driven by MaxSAT reasoning give a tight upper bound for the encoded MWC. The approach is implemented in a branch-and-bound algorithm called MWCLQ. Experimental evaluations on the broadly used DIMACS benchmark, BHOSLIB benchmark, random graphs and the benchmark from the winner determination problem show that our approach allows MWCLQ to reduce the search space significantly and to solve MWC instances effectively. Consequently, MWCLQ outperforms state-of-the-art exact algorithms on the vast majority of instances. Moreover, it is surprisingly effective in solving hard and dense instances.
37
Fomin, Fedor V., and Petr A. Golovach. "Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs." Algorithmica 83, no. 7 (April 11, 2021): 2170–214. http://dx.doi.org/10.1007/s00453-021-00822-x.
Full textAbstract:
AbstractWe study algorithmic properties of the graph class $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e . More precisely, we identify a large class of optimization problems on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e solvable in time $$2^{{\mathcal{O}}(\sqrt{k}\log k)}\cdot n^{{\mathcal{O}}(1)}$$ 2 O ( k log k ) · n O ( 1 ) . Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e , namely, $${\textsc {Interval}}{-ke}$$ I N T E R V A L - k e and $${\textsc {Split}}{-ke}$$ S P L I T - k e graphs.
38
de Melo, Alexsander A., Celina M. H. de Figueiredo, and Uéverton S. Souza. "On the Computational Difficulty of the Terminal Connection Problem." RAIRO - Theoretical Informatics and Applications 57 (2023): 3. http://dx.doi.org/10.1051/ita/2023002.
Full textAbstract:
A connection tree of a graph G for a terminal set W is a tree subgraph T of G such that leaves(T) ⊆ W ⊆ V(T). A non-terminal vertex is called linker if its degree in T is exactly 2, and it is called router if its degree in T is at least 3. The Terminal connection problem (TCP) asks whether G admits a connection tree for W with at most ℓ linkers and at most r routers, while the Steiner tree problem asks whether G admits a connection tree for W with at most k non-terminal vertices. We prove that, if r ≥ 1 is fixed, then TCP is polynomial-time solvable when restricted to split graphs. This result separates the complexity of TCP from the complexity of Steiner tree, which is known to be NP-complete on split graphs. Additionally, we prove that TCP is NP-complete on strongly chordal graphs, even if r ≥ 0 is fixed, whereas Steiner tree is known to be polynomial-time solvable. We also prove that, when parameterized by clique-width, TCP is W[1]-hard, whereas STeiner tree is known to be in FPT. On the other hand, agreeing with the complexity of Steiner tree, we prove that TCP is linear-time solvable when restricted to cographs (i.e. graphs of clique-width 2). Finally, we prove that, even if either ℓ ≥ 0 or r ≥ 0 is fixed, TCP remains NP-complete on graphs of maximum degree 3.
39
Maksimenko, Aleksandr N. "Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm." Modeling and Analysis of Information Systems 27, no. 1 (March 23, 2020): 72–85. http://dx.doi.org/10.18255/1818-1015-2020-1-72-85.
Full textAbstract:
In this paper, we consider the notion of a direct type algorithm introduced by V. A. Bondarenko in 1983. A direct type algorithm is a linear decision tree with some special properties. the concept of a direct type algorithm is determined using the graph of solutions of a combinatorial optimization problem. e vertices of this graph are all feasible solutions of a problem. Two solutions are called adjacent if there are input data for which these and only these solutions are optimal. A key feature of direct type algorithms is that their complexity is bounded from below by the clique number of the solutions graph. In 2015-2018, there were five papers published, the main results of which are estimates of the clique numbers of polyhedron graphs associated with various combinatorial optimization problems. the main motivation in these works is the thesis that the class of direct type algorithms is wide and includes many classical combinatorial algorithms, including the branch and bound algorithm for the traveling salesman problem, proposed by J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel in 1963. We show that this algorithm is not a direct type algorithm. Earlier, in 2014, the author of this paper showed that the Hungarian algorithm for the assignment problem is not a direct type algorithm. us, the class of direct type algorithms is not so wide as previously assumed.
40
Zhou, Yi, Shan Hu, Mingyu Xiao, and Zhang-Hua Fu. "Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 14 (May 18, 2021): 12453–60. http://dx.doi.org/10.1609/aaai.v35i14.17477.
Full textAbstract:
In a graph, a k-plex is a vertex set in which every vertex is not adjacent to at most k vertices of this set. The maximum k-plex problem, which asks for the largest k-plex from the given graph, is a key primitive in a variety of real-world applications like community detection and so on. In the paper, we develop an exact algorithm, Maplex, for solving this problem in real world graphs practically. Based on the existing first-order and the novel second-order reduction rules, we design a powerful preprocessing method which efficiently removes redundant vertices and edges for Maplex. Also, the graph color heuristic is widely used for overestimating the maximum clique of a graph. For the first time, we generalize this technique for bounding the size of maximum k-plex in Maplex. Experiments are carried out to compare our algorithm with other state-of-the-art solvers on a wide range of publicly available graphs. Maplex outperforms all other algorithms on large real world graphs and is competitive with existing solvers on artificial dense graphs. Finally, we shed light on the effectiveness of each key component of Maplex.
41
Karapetyan, Iskandar. "On the restrictive channel thickness estimation." Facta universitatis - series: Electronics and Energetics 20, no. 3 (2007): 499–506. http://dx.doi.org/10.2298/fuee0703499k.
Full textAbstract:
Channel routing is an important phase of physical design of LSI and VLSI chips. The channel routing method was first proposed by Akihiro Hashimoto and James Stevens [1]. The method was extensively studied by many authors and applied to different technologies. At present there are known many effective heuristic algorithms for channel routing. A. LaPaugh [2] proved that the restrictive routing problem is NP-complete. In this paper we prove that for every positive integer k there is a restrictive channel C for which ?(C)>? (HG)+L(VG)+k, where ? (C) is the thickness of the channel, ?(HG) is clique number of the horizontal constraints graph HG and L(VG) is the length of the longest directed path in the vertical constraints graph VG.
42
Koutris, Paraschos, and Shaleen Deep. "The Fine-Grained Complexity of CFL Reachability." Proceedings of the ACM on Programming Languages 7, POPL (January 9, 2023): 1713–39. http://dx.doi.org/10.1145/3571252.
Full textAbstract:
Many problems in static program analysis can be modeled as the context-free language (CFL) reachability problem on directed labeled graphs. The CFL reachability problem can be generally solved in time O ( n 3 ), where n is the number of vertices in the graph, with some specific cases that can be solved faster. In this work, we ask the following question: given a specific CFL, what is the exact exponent in the monomial of the running time? In other words, for which cases do we have linear, quadratic or cubic algorithms, and are there problems with intermediate runtimes? This question is inspired by recent efforts to classify classic problems in terms of their exact polynomial complexity, known as fine-grained complexity. Although recent efforts have shown some conditional lower bounds (mostly for the class of combinatorial algorithms), a general picture of the fine-grained complexity landscape for CFL reachability is missing. Our main contribution is lower bound results that pinpoint the exact running time of several classes of CFLs or specific CFLs under widely believed lower bound conjectures (e.g., Boolean Matrix Multiplication, k -Clique, APSP, 3SUM). We particularly focus on the family of Dyck- k languages (which are strings with well-matched parentheses), a fundamental class of CFL reachability problems. Remarkably, we are able to show a Ω( n 2.5 ) lower bound for Dyck-2 reachability, which to the best of our knowledge is the first super-quadratic lower bound that applies to all algorithms, and shows that CFL reachability is strictly harder that Boolean Matrix Multiplication. We also present new lower bounds for the case of sparse input graphs where the number of edges m is the input parameter, a common setting in the database literature. For this setting, we show a cubic lower bound for Andersen’s Pointer Analysis which significantly strengthens prior known results.
43
Buchin, Kevin, Sariel Har-Peled, and Dániel Oláh. "A Spanner for the Day After." Discrete & Computational Geometry 64, no. 4 (August 6, 2020): 1167–91. http://dx.doi.org/10.1007/s00454-020-00228-6.
Full textAbstract:
AbstractWe show how to construct a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner over a set $${P}$$ P of n points in $${\mathbb {R}}^d$$ R d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $${\vartheta },\varepsilon \in (0,1)$$ ϑ , ε ∈ ( 0 , 1 ) , the computed spanner $${G}$$ G has $$\begin{aligned} {{\mathcal {O}}}\bigl (\varepsilon ^{-O(d)} {\vartheta }^{-6} n(\log \log n)^6 \log n \bigr ) \end{aligned}$$ O ( ε - O ( d ) ϑ - 6 n ( log log n ) 6 log n ) edges. Furthermore, for anyk, and any deleted set $${{B}}\subseteq {P}$$ B ⊆ P of k points, the residual graph $${G}\setminus {{B}}$$ G \ B is a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner for all the points of $${P}$$ P except for $$(1+{\vartheta })k$$ ( 1 + ϑ ) k of them. No previous constructions, beyond the trivial clique with $${{\mathcal {O}}}(n^2)$$ O ( n 2 ) edges, were known with this resilience property (i.e., only a tiny additional fraction of vertices, $$\vartheta |B|$$ ϑ | B | , lose their distance preserving connectivity). Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black-box fashion.
44
Gunda, Spoorthy, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. "On the Parameterized Approximability of Contraction to Classes of Chordal Graphs." ACM Transactions on Computation Theory 13, no. 4 (December 31, 2021): 1–40. http://dx.doi.org/10.1145/3470869.
Full textAbstract:
A graph operation that contracts edges is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contracting k edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely, the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly difficult than one might expect. In this article, we study the F -Contraction problem, where F is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph G and an integer k , F -Contraction asks whether there exists X ⊆ E(G) such that G/X ∈ F and | X | ≤ k . Here, G/X is the graph obtained from G by contracting edges in X . We obtain the following results for the F - Contraction problem: • Clique Contraction is known to be FPT . However, unless NP⊆ coNP/ poly , it does not admit a polynomial kernel. We show that it admits a polynomial-size approximate kernelization scheme ( PSAKS ). That is, it admits a (1 + ε)-approximate kernel with O ( k f(ε)) vertices for every ε > 0. • Split Contraction is known to be W[1]-Hard . We deconstruct this intractability result in two ways. First, we give a (2+ε)-approximate polynomial kernel for Split Contraction (which also implies a factor (2+ε)- FPT -approximation algorithm for Split Contraction ). Furthermore, we show that, assuming Gap-ETH , there is no (5/4-δ)- FPT -approximation algorithm for Split Contraction . Here, ε, δ > 0 are fixed constants. • Chordal Contraction is known to be W[2]-Hard . We complement this result by observing that the existing W[2]-hardness reduction can be adapted to show that, assuming FPT ≠ W[1] , there is no F(k) - FPT -approximation algorithm for Chordal Contraction . Here, F(k) is an arbitrary function depending on k alone. We say that an algorithm is an h(k) - FPT -approximation algorithm for the F -Contraction problem, if it runs in FPT time, and on any input (G, k) such that there exists X ⊆ E(G) satisfying G/X ∈ F and | X | ≤ k , it outputs an edge set Y of size at most h(k) ċ k for which G/Y is in F .
45
Pandurangan, Gopal, Peter Robinson, and Michele Scquizzato. "On the Distributed Complexity of Large-Scale Graph Computations." ACM Transactions on Parallel Computing 8, no. 2 (June 30, 2021): 1–28. http://dx.doi.org/10.1145/3460900.
Full textAbstract:
Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k ≥ 2 machines jointly perform computations on graphs with n nodes (typically, n >> k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main contribution is the General Lower Bound Theorem , a theorem that can be used to show non-trivial lower bounds on the round complexity of distributed large-scale data computations. This result is established via an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines to solve the problem. Our approach is generic, and this theorem can be used in a “cookbook” fashion to show distributed lower bounds for several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds on the round complexity of two fundamental graph problems, namely, PageRank computation and triangle enumeration . These applications show that our approach can yield lower bounds for problems where the application of communication complexity techniques seems not obvious or gives weak bounds, including and especially under a stochastic partition of the input. We then present distributed algorithms for PageRank and triangle enumeration with a round complexity that (almost) matches the respective lower bounds; these algorithms exhibit a round complexity that scales superlinearly in k , improving significantly over previous results [Klauck et al., SODA 2015]. Specifically, we show the following results: PageRank: We show a lower bound of Ὼ(n/k 2 ) rounds and present a distributed algorithm that computes an approximation of the PageRank of all the nodes of a graph in Õ(n/k 2 ) rounds. Triangle enumeration: We show that there exist graphs with m edges where any distributed algorithm requires Ὼ(m/k 5/3 ) rounds. This result also implies the first non-trivial lower bound of Ὼ(n 1/3 ) rounds for the congested clique model, which is tight up to logarithmic factors. We then present a distributed algorithm that enumerates all the triangles of a graph in Õ(m/k 5/3 + n/k 4/3 ) rounds.
46
Chang, Lijun, Mouyi Xu, and Darren Strash. "Efficient maximum k -plex computation over large sparse graphs." Proceedings of the VLDB Endowment 16, no. 2 (October 2022): 127–39. http://dx.doi.org/10.14778/3565816.3565817.
Full textAbstract:
The k -plex model is a relaxation of the clique model by allowing every vertex to miss up to k neighbors. Designing exact and efficient algorithms for computing a maximum k -plex in a graph has been receiving increasing interest recently. However, the existing algorithms are still inefficient due to having major limitations. We in this paper design a new algorithm kPlexS for the maximum k -plex problem, with three novel contributions. Firstly, we propose a new framework for computing maximum k -plex over large sparse graphs, by iteratively extracting small dense subgraphs from it and then solving each of the extracted dense subgraphs by a branch-and-bound search. Secondly, we propose an efficient reduction algorithm CTCP to reduce the input graph size by exhaustively conducting vertex reduction and edge reduction. CTCP computes a smaller reduced graph and also has a lower time complexity than the existing techniques. Moreover, we iteratively invoke CTCP to reduce the input graph once a vertex has been processed and removed from it. Thirdly, we develop a branch-and-bound algorithm BBMatrix specifically targeting the dense subgraphs that are extracted from the input graph. BBMatrix represents its input graph by an adjacency matrix, and utilizes both first-order (i.e., individual vertices) and second-order information (i.e., pairs of vertices) for reduction and upper bounding. In addition, incremental techniques are proposed to efficiently apply the reduction and upper bounding during the recursion. Extensive empirical studies on large real graphs demonstrate that our algorithm kPlexS outperforms the state-of-the-art algorithms BnB, Maplex, and KpLeX.
47
Vilakone, Phonexay, and Doo-Soon Park. "The Efficiency of a DoParallel Algorithm and an FCA Network Graph Applied to Recommendation System." Applied Sciences 10, no. 8 (April 23, 2020): 2939. http://dx.doi.org/10.3390/app10082939.
Full textAbstract:
This article investigates the efficiency of a doParallel algorithm and a formal concept analysis (FCA) network graph applied to recommendation systems. It is the first article using the FCA method to create a network graph and apply this graph to improve the accuracy of a recommendation system. According to the fundamental knowledge about users who have similar feature information, they may like the same items. This idea was used to create an FCA network graph. In the proposed process, the k-clique method was used to divide this network graph into various communities. A combination of the k-nearest neighbor and the betweenness centrality methods was used to find a suitable community for a new user based on the feature information similarities between the new user and an existing user in each community. Finally, a data mining method created a list of items from suitable communities and recommended them to the new user. In essence, the execution in this article uses a doParallel algorithm as a mechanism in parallel processing technology. The result of the implementation is satisfactory. It proved that the proposed method could resolve the cold-start problem in a recommendation system and may overcome the vast time consumption when a huge dataset is involved.
48
Coniglio, Stefano, and Stefano Gualandi. "Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming." INFORMS Journal on Computing 34, no. 2 (March 2022): 1006–23. http://dx.doi.org/10.1287/ijoc.2021.1115.
Full textAbstract:
In the context of the maximum stable set problem, rank inequalities impose that the cardinality of any set of vertices contained in a stable set be, at most, as large as the stability number of the subgraph induced by such a set. Rank inequalities are very general, as they subsume many classical inequalities such as clique, hole, antihole, web, and antiweb inequalities. In spite of their generality, the exact separation of rank inequalities has never been addressed without the introduction of topological restrictions on the induced subgraph and the tightness of their closure has never been investigated systematically. In this work, we propose a methodology for optimizing over the closure of all rank inequalities with a right-hand side no larger than a small constant without imposing any restrictions on the topology of the induced subgraph. Our method relies on the exact separation of a relaxation of rank inequalities, which we call relaxed k-rank inequalities, whose closure is as tight. We investigate the corresponding separation problem, a bilevel programming problem asking for a subgraph of maximum weight with a bound on its stability number, whose study could be of independent interest. We first prove that the problem is [Formula: see text]-hard and provide some insights on its polyhedral structure. We then propose two exact methods for its solution: a branch-and-cut algorithm (which relies on a family of faced-defining inequalities which we introduce in this paper) and a purely combinatorial branch-and-bound algorithm. Our computational results show that the closure of rank inequalities with a right-hand side no larger than a small constant can yield a bound that is stronger, in some cases, than Lovász’s Theta function, and substantially stronger than bounds obtained with standard inequalities that are valid for the stable set problem, including odd-cycle inequalities and wheel inequalities. Summary of Contribution: This paper proposes two original methods for solving a challenging cut-separation problem (of bilevel type) for a large class of inequalities valid for one of the key operations research problems, namely, the max stable set problem. An extensive set of experimental results validates the proposed methods. All the source code and data sets are available online on GitHub.
49
Bhasker, J., and Tariq Samad. "The clique-partitioning problem." Computers & Mathematics with Applications 22, no. 6 (1991): 1–11. http://dx.doi.org/10.1016/0898-1221(91)90001-k.
Full text
50
GANDHI, RAJIV, BRADFORD GREENING, SRIRAM PEMMARAJU, and RAJIV RAMAN. "SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS." Discrete Mathematics, Algorithms and Applications 02, no. 03 (September 2010): 331–45. http://dx.doi.org/10.1142/s1793830910000693.
Full textAbstract:
In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O( log n)-approximation algorithm for it.