More Like this

1. Turning Cliques into Paths to Achieve Planarity

   https://doi.org/10.1007/978-3-030-04414-5_5  

   Angelini, P.; Eades, P.; Hong, S.; Klein, K.; Kobourov, S.; Liotta, G.; Navarra, A.; Tappini, A. (January 2018, International Symposium on Graph Drawing and Network Visualization)

   Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call ℎ-Clique2Path Planarity: Given a graph G, whose vertices are partitioned into subsets of size at most h, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of G is planar. We study this problem when G is a simple topological graph, and establish its complexity in relation to k-planarity. We prove that ℎ-Clique2Path Planarity is NP-complete even when ℎ=4 and G is a simple 3-plane graph, while it can be solved in linear time, for any h, when G is 1-plane. 

   more » « less
2. Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach

   https://doi.org/10.14778/3436905.3436916  

   Guo, Guimu; Yan, Da; Özsu, M. Tamer; Jiang, Zhe; Khalil, Jalal (January 2020, Proceedings of the VLDB Endowment)

   null (Ed.)

   Given a user-specified minimum degree threshold γ, a γ-quasi-clique is a subgraph g = (Vg, Eg) where each vertex ν ∈ Vg connects to at least γ fraction of the other vertices (i.e., ⌈γ · (|Vg|- 1)⌉ vertices) in g. Quasi-clique is one of the most natural definitions for dense structures useful in finding communities in social networks and discovering significant biomolecule structures and pathways. However, mining maximal quasi-cliques is notoriously expensive. In this paper, we design parallel algorithms for mining maximal quasi-cliques on G-thinker, a distributed graph mining framework that decomposes mining into compute-intensive tasks to fully utilize CPU cores. We found that directly using G-thinker results in the straggler problem due to (i) the drastic load imbalance among different tasks and (ii) the difficulty of predicting the task running time. We address these challenges by redesigning G-thinker's execution engine to prioritize long-running tasks for execution, and by utilizing a novel timeout strategy to effectively decompose long-running tasks to improve load balancing. While this system redesign applies to many other expensive dense subgraph mining problems, this paper verifies the idea by adapting the state-of-the-art quasi-clique algorithm, Quick, to our redesigned G-thinker. Extensive experiments verify that our new solution scales well with the number of CPU cores, achieving 201× runtime speedup when mining a graph with 3.77M vertices and 16.5M edges in a 16-node cluster. 

   more » « less
3. A Note on the Gyárfás–Sumner Conjecture

   https://doi.org/10.1007/s00373-024-02754-z  

   Nguyen, Tung; Scott, Alex; Seymour, Paul (April 2024, Graphs and Combinatorics)

   The Gyárfás–Sumner conjecture says that for every tree T and every integer t ≥ 1, if G is a graph with no clique of size t and with sufficiently large chromatic number, then G contains an induced subgraph isomorphic to T. This remains open, but we prove that under the same hypotheses, G contains a subgraph H isomorphic to T that is “path-induced”; that is, for some distinguished vertex r, every path of H with one end r is an induced path of G. 

   more » « less
4. Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles

   Bresler, Guy; Guo, Chenghao; Polyanskiy, Yury (January 2023, Symposium on foundations of computer science)

   We aim to understand the extent to which the noise distribution in a planted signal-plusnoise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erd˝os-R´enyi G(n, p), which has independent edges, we take the ambient graph to be the random graph with triangles (RGT) obtained by adding triangles to G(n, p). We show that the RGT can be efficiently mapped to the corresponding G(n, p), and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erd˝os-R´enyi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations. 

   more » « less
5. Query Complexity of Stochastic Minimum Vertex Cover

   https://doi.org/10.4230/LIPIcs.ITCS.2025.41  

   Derakhshan, Mahsa; Saneian, Mohammad; Xun, Zhiyang (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We study the stochastic minimum vertex cover problem for general graphs. In this problem, we are given a graph G=(V, E) and an existence probability p_e for each edge e ∈ E. Edges of G are realized (or exist) independently with these probabilities, forming the realized subgraph H. The existence of an edge in H can only be verified using edge queries. The goal of this problem is to find a near-optimal vertex cover of H using a small number of queries. Previous work by Derakhshan, Durvasula, and Haghtalab [STOC 2023] established the existence of 1.5 + ε approximation algorithms for this problem with O(n/ε) queries. They also show that, under mild correlation among edge realizations, beating this approximation ratio requires querying a subgraph of size Ω(n ⋅ RS(n)). Here, RS(n) refers to Ruzsa-Szemerédi Graphs and represents the largest number of induced edge-disjoint matchings of size Θ(n) in an n-vertex graph. In this work, we design a simple algorithm for finding a (1 + ε) approximate vertex cover by querying a subgraph of size O(n ⋅ RS(n)) for any absolute constant ε > 0. Our algorithm can tolerate up to O(n ⋅ RS(n)) correlated edges, hence effectively completing our understanding of the problem under mild correlation. 

   more » « less