Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth
91
0
0.0
(
0
)
Added by
Jianhua Tu
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a graph $G=(V,E)$ and a positive integer $tgeq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $Fsubseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$. The $VCP_t$ problem is NP-complete for any integer $tgeq2$ and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time $4^pcdot n^{O(1)}$ for the $VCP_3$ problem on $n$-vertex graphs with treewidth $p$. In this paper, we propose an improvement of it and improved the time-complexity to $3^pcdot n^{O(1)}$. The connected vertex cover $P_3$ ($CVCP_3$) problem is the connected variation of the $VCP_3$ problem where $G[F]$ is required to be connected. Using the Cut&Count technique, we give a randomized algorithm with runtime $4^pcdot n^{O(1)}$ for the $CVCP_3$ problem on $n$-vertex graphs with treewidth $p$.
rate research
Read More
We focus on counting the number of labeled graphs on $n$ vertices and treewidth at most $k$ (or equivalently, the number of labeled partial $k$-trees), which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been studied. We show that $$ left(c cdot frac{kcdot 2^k cdot n}{log k} right)^n cdot 2^{-frac{k(k+3)}{2}} cdot k^{-2k-2} leq T_{n,k} leq left(k cdot 2^k cdot nright)^n cdot 2^{-frac{k(k+1)}{2}} cdot k^{-k}, $$ for $k > 1$ and some explicit absolute constant $c > 0$. The upper bound is an immediate consequence of the well-known number of labeled $k$-trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most $k$.
The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the total weight of edges between the two sets is maximized/minimized. Although these two problems are known to be NP-hard, there is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen et al. (SIAM J. Comput. 2005) gave an $O(2^tn^3)$-time algorithm when given a tree decomposition of width $t$ of the input graph, where $n$ is the number of vertices of the input graph. Eiben et al. (ESA 2019) improved the dependency of $n$ in the running time by giving an $O(8^tt^5n^2log n)$-time algorithm. Moreover, they showed that there is no $O(n^{2-varepsilon})$-time algorithm for trees under some reasonable complexity assumption. In this paper, we show an $O(2^t(tn)^2)$-time algorithm for both problems, which is asymptotically tight to their conditional lower bound. We also show that the exponential dependency of the treewidth is asymptotically optimal under the Strong Exponential Time Hypothesis. Finally, we discuss the (in)tractability of both problems with respect to special graph classes.
After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover. Here we consider the TREEWIDTH and PATHWIDTH problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the PATHWIDTH and TREEWIDTH can be computed in O*(3^k) time. This complements recent polynomial kernel results for TREEWIDTH and PATHWIDTH parameterized by the Vertex Cover.
A (vertex) $ell$-ranking is a labelling $varphi:V(G)tomathbb{N}$ of the vertices of a graph $G$ with integer colours so that for any path $u_0,ldots,u_p$ of length at most $ell$, $varphi(u_0) eqvarphi(u_p)$ or $varphi(u_0)<max{varphi(u_0),ldots,varphi(u_p)}$. We show that, for any fixed integer $ellge 2$, every $n$-vertex planar graph has an $ell$-ranking using $O(log n/logloglog n)$ colours and this is tight even when $ell=2$; for infinitely many values of $n$, there are $n$-vertex planar graphs, for which any 2-ranking requires $Omega(log n/logloglog n)$ colours. This result also extends to bounded genus graphs. In developing this proof we obtain optimal bounds on the number of colours needed for $ell$-ranking graphs of treewidth $t$ and graphs of simple treewidth $t$. These upper bounds are constructive and give $O(nlog n)$-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for $ell$-rankings of apex minor-free graphs and $k$-planar graphs.
We initiate the study of coresets for clustering in graph metrics, i.e., the shortest-path metric of edge-weighted graphs. Such clustering problems are essential to data analysis and used for example in road networks and data visualization. A coreset is a compact summary of the data that approximately preserves the clustering objective for every possible center set, and it offers significant efficiency improvements in terms of running time, storage, and communication, including in streaming and distributed settings. Our main result is a near-linear time construction of a coreset for k-Median in a general graph $G$, with size $O_{epsilon, k}(mathrm{tw}(G))$ where $mathrm{tw}(G)$ is the treewidth of $G$, and we complement the construction with a nearly-tight size lower bound. The construction is based on the framework of Feldman and Langberg [STOC 2011], and our main technical contribution, as required by this framework, is a uniform bound of $O(mathrm{tw}(G))$ on the shattering dimension under any point weights. We validate our coreset on real-world road networks, and our scalable algorithm constructs tiny coresets with high accuracy, which translates to a massive speedup of existing approximation algorithms such as local search for graph k-Median.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
