Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
111
0
0.0
(
0
)
Added by
Dimitrios Thilikos
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In general, a graph modification problem is defined by a graph modification operation $boxtimes$ and a target graph property ${cal P}$. Typically, the modification operation $boxtimes$ may be vertex removal}, edge removal}, edge contraction}, or edge addition and the question is, given a graph $G$ and an integer $k$, whether it is possible to transform $G$ to a graph in ${cal P}$ after applying $k$ times the operation $boxtimes$ on $G$. This problem has been extensively studied for particilar instantiations of $boxtimes$ and ${cal P}$. In this paper we consider the general property ${cal P}_{{phi}}$ of being planar and, moreover, being a model of some First-Order Logic sentence ${phi}$ (an FOL-sentence). We call the corresponding meta-problem Graph $boxtimes$-Modification to Planarity and ${phi}$ and prove the following algorithmic meta-theorem: there exists a function $f:Bbb{N}^{2}toBbb{N}$ such that, for every $boxtimes$ and every FOL sentence ${phi}$, the Graph $boxtimes$-Modification to Planarity and ${phi}$ is solvable in $f(k,|{phi}|)cdot n^2$ time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifmans Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.
rate research
Read More
We introduce the problem Synchronized Planarity. Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertices of equal degree by providing a bijection between their edges. Synchronized Planarity then asks whether the graph admits a crossing-free embedding into the plane such that the orders of edges around synchronized vertices are consistent. We show, on the one hand, that Synchronized Planarity can be solved in quadratic time, and, on the other hand, that it serves as a powerful modeling language that lets us easily formulate several constrained planarity problems as instances of Synchronized Planarity. In particular, this lets us solve Clustered Planarity in quadratic time, where the most efficient previously known algorithm has an upper bound of $O(n^{8})$.
In a (parameterized) graph edge modification problem, we are given a graph $G$, an integer $k$ and a (usually well-structured) class of graphs $mathcal{G}$, and ask whether it is possible to transform $G$ into a graph $G in mathcal{G}$ by adding and/or removing at most $k$ edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a $2k$ kernel [Cao, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size $O(k/log k)$. We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH.
In this paper, we show a connection between a certain online low-congestion routing problem and an online prediction of graph labeling. More specifically, we prove that if there exists a routing scheme that guarantees a congestion of $alpha$ on any edge, there exists an online prediction algorithm with mistake bound $alpha$ times the cut size, which is the size of the cut induced by the label partitioning of graph vertices. With previous known bound of $O(log n)$ for $alpha$ for the routing problem on trees with $n$ vertices, we obtain an improved prediction algorithm for graphs with high effective resistance. In contrast to previous approaches that move the graph problem into problems in vector space using graph Laplacian and rely on the analysis of the perceptron algorithm, our proof are purely combinatorial. Further more, our approach directly generalizes to the case where labels are not binary.
We show that the natural Glauber dynamics mixes rapidly and generates a random proper edge-coloring of a graph with maximum degree $Delta$ whenever the number of colors is at least $qgeq (frac{10}{3} + epsilon)Delta$, where $epsilon>0$ is arbitrary and the maximum degree satisfies $Delta geq C$ for a constant $C = C(epsilon)$ depending only on $epsilon$. For edge-colorings, this improves upon prior work cite{Vig99, CDMPP19} which show rapid mixing when $qgeq (frac{11}{3}-epsilon_0 ) Delta$, where $epsilon_0 approx 10^{-5}$ is a small fixed constant. At the heart of our proof, we establish a matrix trickle-down theorem, generalizing Oppenheims influential result, as a new technique to prove that a high dimensional simplical complex is a local spectral expander.
We study the design of local algorithms for massive graphs. A local algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster--a subset of vertices whose internal connections are significantly richer than its external connections--near a given vertex. The running time of our algorithm, when it finds a non-empty local cluster, is nearly linear in the size of the cluster it outputs. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly-linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly-linear time algorithm for solving linear systems in symmetric, diagonally-dominant matrices. The linear system solver also leads to a nearly linear-time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
