Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient Reassembling of Graphs, Part 2: The Balanced Case
52
0
0.0
(
0
)
Added by
Saber Mirzaei
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The reassembling of a simple connected graph G = (V,E) is an abstraction of a problem arising in earlier studies of network analysis. The reassembling process has a simple formulation (there are several equivalent formulations) relative to a binary tree B (reassembling tree), with root node at the top and $n$ leaf nodes at the bottom, where every cross-section corresponds to a partition of V such that: - the bottom (or first) cross-section (all the leaves) is the finest partition of V with n one-vertex blocks, - the top (or last) cross-section (the root) is the coarsest partition with a single block, the entire set V, - a node (or block) in an intermediate cross-section (or partition) is the result of merging its two children nodes (or blocks) in the cross-section (or partition) below it. The maximum edge-boundary degree encountered during the reassembling process is what we call the alpha-measure of the reassembling, and the sum of all edge-boundary degrees is its beta-measure. The alpha-optimization (resp. beta-optimization) of the reassembling of G is to determine a reassembling tree B that minimizes its alpha-measure (resp. beta-measure). There are different forms of reassembling. In an earlier report, we studied linear reassembling, which is the case when the height of B is (n-1). In this report, we study balanced reassembling, when B has height [log n]. The two main results in this report are the NP-hardness of alpha-optimization and beta-optimization of balanced reassembling. The first result is obtained by a sequence of polynomial-time reductions from minimum bisection of graphs (known to be NP-hard), and the second by a sequence of polynomial-time reductions from clique cover of graphs (known to be NP-hard).
rate research
Read More
The reassembling of a simple connected graph G = (V,E) is an abstraction of a problem arising in earlier studies of network analysis. Its simplest formulation is in two steps: (1) We cut every edge of G into two halves, thus obtaining a collection of n=|V| one-vertex components. (2) We splice the two halves of every edge together, not of all the edges at once, but in some ordering Theta of the edges that minimizes two measures that depend on the edge-boundary degrees of assembled components. The edge-boundary degree of a component A (subset of V) is the number of edges in G with one endpoint in A and one endpoint in V-A. We call the maximum edge-boundary degree encountered during the reassembling process the alpha-measure of the reassembling, and the sum of all edge-boundary degrees is its beta-measure. The alpha-optimization (resp. beta-optimization) of the reassembling of G is to determine an order Theta for splicing the edges that minimizes its alpha-measure (resp. beta-measure). There are different forms of reassembling. We consider only cases satisfying the condition that if the an edge between disjoint components A and B is spliced, then all the edges between A and B are spliced at the same time. In this report, we examine the particular case of linear reassembling, which requires that the next edge to be spliced must be adjacent to an already spliced edge. We delay other forms of reassembling to follow-up reports. We prove that alpha-optimization of linear reassembling and minimum-cutwidth linear arrangment (CutWidth) are polynomially reducible to each other, and that beta-optimization of linear reassembling and minimum-cost linear arrangement (MinArr) are polynomially reducible to each other.
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit new simple proofs using the incompressibility method.
We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of $n$ unit disks in the plane there exists a line $ell$ such that $ell$ intersects at most $O(sqrt{(m+n)log{n}})$ disks and each of the halfplanes determined by $ell$ contains at most $2n/3$ unit disks from the set, where $m$ is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting $O(sqrt{m+n})$ disks exists, but each halfplane may contain up to $4n/5$ disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in $n$ exists when we look at disks of arbitrary radii, even when $m=0$. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size $O(sqrt{m})$).
A function $f:[n_1]timesdotstimes[n_d]tomathbb{F}_2$ is a direct sum if it is of the form $fleft(a_1,dots,a_dright) = f_1(a_1)oplusdots oplus f_d (a_d),$ for some $d$ functions $f_i:[n_i]tomathbb{F}_2$ for all $i=1,dots, d$, and where $n_1,dots,n_dinmathbb{N}$. We present a $4$-query test which distinguishes between direct sums and functions that are far from them. The test relies on the BLR linearity test (Blum, Luby, Rubinfeld, 1993) and on an agreement test which slightly generalizes the direct product test (Dinur, Steurer, 2014). In multiplicative $pm 1$ notation, our result reads as follows. A $d$-dimensional tensor with $pm 1$ entries is called a tensor product if it is a tensor product of $d$ vectors with $pm 1$ entries, or equivalently, if it is of rank $1$. The presented tests can be read as tests for distinguishing between tensor products and tensors that are far from being tensor products. We also present a different test, which queries the function at most $(d+2)$ times, but is easier to analyze.
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular arcs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
