An official website of the United States government
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
Quasipolynomiality of the Smallest Missing Induced Subgraph
We study the problem of finding the smallest graph that does not occur as an induced subgraph of a given graph. This missing induced subgraph has at most logarithmic size and can be found by a brute-force search, in an $$n$$-vertex graph, in time $$n^{O(\log n)}$$. We show that under the Exponential Time Hypothesis this quasipolynomial time bound is optimal. We also consider variations of the problem in which either the missing subgraph or the given graph comes from a restricted graph family; for instance, we prove that the smallest missing planar induced subgraph of a given planar graph can be found in polynomial time.
more »
« less
- Award ID(s):
- 2212129
- PAR ID:
- 10545600
- Publisher / Repository:
- Brown
- Date Published:
- Journal Name:
- Journal of Graph Algorithms and Applications
- Volume:
- 27
- Issue:
- 5
- ISSN:
- 1526-1719
- Page Range / eLocation ID:
- 329-339
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
null (Ed.)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.more » « less
-
Beyersdorff, Olaf; Kanté, Mamadou Moustapha; Kupferman, Orna; Lokshtanov, Daniel (Ed.)We revisit the recent polynomial-time algorithm for the Max Weight Independent Set (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Chudnovsky, Dibek, Rzążewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time n^{𝒪(Δ²)}, where n is the number of vertices of the instance and Δ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph.more » « less
-
The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. Specifically, we observe an undirected and unweighted graph on n vertices. Under the null hypothesis, the graph is a realization of an Erdös-R{\'e}nyi graph with edge probability (or, density) q. Under the alternative, there is a subgraph on k vertices with edge probability p>q. The statistical as well as the computational barriers of this problem are well-understood for a wide range of the edge parameters p and q. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph. We also propose a polynomial-time algorithm which is able to detect the planted subgraph, albeit with more queries compared to the above lower bound. We conjecture that in the leftover regime, no polynomial-time algorithms exist. Our results resolve two open questions posed in the past literature.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.7155/jgaa.00625
