Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMimicking Networks Parameterized by Connectivity
69
0
0.0
(
0
)
Added by
Daniel Vaz
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a graph $G=(V,E)$, capacities $w(e)$ on edges, and a subset of terminals $mathcal{T} subseteq V: |mathcal{T}| = k$, a mimicking network for $(G,mathcal{T})$ is a graph $(H,w)$ that contains copies of $mathcal{T}$ and preserves the value of minimum cuts separating any subset $A, B subseteq mathcal{T}$ of terminals. Mimicking networks of size $2^{2^k}$ are known to exist and can be constructed algorithmically, while the best known lower bound is $2^{Omega(k)}$; therefore, an exponential size is required if one aims at preserving cuts exactly. In this paper, we study mimicking networks that preserve connectivity of the graph exactly up to the value of $c$, where $c$ is a parameter. This notion of mimicking network is sufficient for some applications, as we will elaborate. We first show that a mimicking of size $3^c cdot k$ exists, that is, we can preserve cuts with small capacity using a network of size linear in $k$. Next, we show an algorithm that finds such a mimicking network in time $2^{O(c^2)} operatorname{poly}(m)$.
rate research
Read More
We study two variants of textsc{Maximum Cut}, which we call textsc{Connected Maximum Cut} and textsc{Maximum Minimal Cut}, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity requirements. Both problems are known to be NP-complete even on planar graphs whereas textsc{Maximum Cut} on planar graphs is solvable in polynomial time. We first show that these problems are NP-complete even on planar bipartite graphs and split graphs. Then we give parameterized algorithms using graph parameters such as clique-width, tree-width, and twin-cover number. Finally, we obtain FPT algorithms with respect to the solution size.
Given a capacitated undirected graph $G=(V,E)$ with a set of terminals $K subset V$, a mimicking network is a smaller graph $H=(V_H,E_H)$ that exactly preserves all the minimum cuts between the terminals. Specifically, the vertex set of the sparsifier $V_H$ contains the set of terminals $K$ and for every bipartition $U, K-U $ of the terminals $K$, the size of the minimum cut separating $U$ from $K-U$ in $G$ is exactly equal to the size of the minimum cut separating $U$ from $K-U$ in $H$. This notion of a mimicking network was introduced by Hagerup, Katajainen, Nishimura and Ragde (1995) who also exhibited a mimicking network of size $2^{2^{k}}$ for every graph with $k$ terminals. The best known lower bound on the size of a mimicking network is linear in the number of terminals. More precisely, the best known lower bound is $k+1$ for graphs with $k$ terminals (Chaudhuri et al. 2000). In this work, we improve both the upper and lower bounds reducing the doubly-exponential gap between them to a single-exponential gap. Specifically, we obtain the following upper and lower bounds on mimicking networks: 1) Given a graph $G$, we exhibit a construction of mimicking network with at most $(|K|-1)$th Dedekind number ($approx 2^{{(k-1)} choose {lfloor {{(k-1)}/2} rfloor}}$) of vertices (independent of size of $V$). Furthermore, we show that the construction is optimal among all {it restricted mimicking networks} -- a natural class of mimicking networks that are obtained by clustering vertices together. 2) There exists graphs with $k$ terminals that have no mimicking network of size smaller than $2^{frac{k-1}{2}}$. We also exhibit improved constructions of mimicking networks for trees and graphs of bounded tree-width.
We study the problem of Imbalance parameterized by the twin cover of a graph. We show that Imbalance is XP parameterized by twin cover, and FPT when parameterized by the twin cover and the size of the largest clique outside the twin cover. In contrast, we introduce a notion of succinct representations of graphs in terms of their twin cover and demonstrate that Imbalance is NP-hard in the setting of succinct representations, even for graphs that have a twin cover of size one.
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.
Let $mathbb{F}[X]$ be the polynomial ring over the variables $X={x_1,x_2, ldots, x_n}$. An ideal $I=langle p_1(x_1), ldots, p_n(x_n)rangle$ generated by univariate polynomials ${p_i(x_i)}_{i=1}^n$ is a emph{univariate ideal}. We study the ideal membership problem for the univariate ideals and show the following results. item Let $f(X)inmathbb{F}[ell_1, ldots, ell_r]$ be a (low rank) polynomial given by an arithmetic circuit where $ell_i : 1leq ileq r$ are linear forms, and $I=langle p_1(x_1), ldots, p_n(x_n)rangle$ be a univariate ideal. Given $vec{alpha}in {mathbb{F}}^n$, the (unique) remainder $f(X) pmod I$ can be evaluated at $vec{alpha}$ in deterministic time $d^{O(r)}cdot poly(n)$, where $d=max{deg(f),deg(p_1)ldots,deg(p_n)}$. This yields an $n^{O(r)}$ algorithm for minimum vertex cover in graphs with rank-$r$ adjacency matrices. It also yields an $n^{O(r)}$ algorithm for evaluating the permanent of a $ntimes n$ matrix of rank $r$, over any field $mathbb{F}$. Over $mathbb{Q}$, an algorithm of similar run time for low rank permanent is due to Barvinok[Bar96] via a different technique. item Let $f(X)inmathbb{F}[X]$ be given by an arithmetic circuit of degree $k$ ($k$ treated as fixed parameter) and $I=langle p_1(x_1), ldots, p_n(x_n)rangle$. We show in the special case when $I=langle x_1^{e_1}, ldots, x_n^{e_n}rangle$, we obtain a randomized $O^*(4.08^k)$ algorithm that uses $poly(n,k)$ space. item Given $f(X)inmathbb{F}[X]$ by an arithmetic circuit and $I=langle p_1(x_1), ldots, p_k(x_k) rangle$, membership testing is $W[1]$-hard, parameterized by $k$. The problem is $MINI[1]$-hard in the special case when $I=langle x_1^{e_1}, ldots, x_k^{e_k}rangle$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
