An official website of the United States government
When interacting with a visualization of a bipartite graph, one of the most common tasks requires identifying the neighbors of a given vertex. In interactive visualizations, selecting a vertex of interest usually highlights the edges to its neighbors while hiding/shading the rest of the graph. If the graph is large, the highlighted subgraph may not fit in the display window. This motivates a natural optimization task: find an arrangement of the vertices along two layers that reduces the size of the window needed to see a selected vertex and all its neighbors. We consider two variants of the problem; for one we present an efficient algorithm, while for the other we show NP-hardness and give a 2-approximation.
more »
« less
Visualization of Bipartite Graphs in Limited Window Size
Bipartite graphs are commonly used to visualize objects and their features. An object may possess several features and several objects may share a common feature. The standard visualization of bipartite graphs, with objects and features on two (say horizontal) parallel lines at integer coordinates and edges drawn as line segments, can often be difficult to work with. A common task in visualization of such graphs is to consider one object and all its features. This naturally defines a drawing window, defined as the smallest interval that contains the x-coordinates of the object and all its features. We show that if both objects and features can be reordered, minimizing the average window size is NP-hard. However, if the features are fixed, then we provide an efficient polynomial time algorithm for arranging the objects, so as to minimize the average window size. Finally, we introduce a different way of visualizing the bipartite graph, by placing the nodes of the two parts on two con- centric circles. For this setting we also show NP-hardness for the general case and a polynomial time algorithm when the features are fixed.
more »
« less
- Award ID(s):
- 2212130
- PAR ID:
- 10493400
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- 49th Intl. Conference on Current Trends in Theory and Practice of Computer Science (SofSem)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Meka, Raghu (Ed.)While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might hope to compress the object into a more succinct representation. An efficient algorithm (with respect to the compressed input size) could then lead to more efficient computations than algorithms taking the explicit, uncompressed object as input. This leads to a natural question: when does knowing the input instance has a more succinct representation make computation easier? We initiate the study of the computational complexity of problems on factored graphs: graphs that are given as a formula of products and unions on smaller graphs. For any graph problem, we define a parameterized version that takes factored graphs as input, parameterized by the number of (smaller) ordinary graphs used to construct the factored graph. In this setting, we characterize the parameterized complexity of several natural graph problems, exhibiting a variety of complexities. We show that a decision version of lexicographically first maximal independent set is XP-complete, and therefore unconditionally not fixed-parameter tractable (FPT). On the other hand, we show that clique counting is FPT. Finally, we show that reachability is XNL-complete. Moreover, XNL is contained in FPT if and only if NL is contained in some fixed polynomial time.more » « less
-
We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model M and a sampling oracle for the distribution \mu_{M^*} of an unknown model M^*, can we efficiently determine if the two models M and M^* are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the Ising model and proper colorings, and explore whether identity testing is any easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalasis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. In particular, for n-vertex graphs of maximum degree d, we prove that if |\beta| d = \omega(\log n) (where \beta is the inverse temperature parameter), then there is no identity testing algorithm for the antiferromagnetic Ising model that runs in polynomial time unless RP = NP. We also establish computational lower bounds for a broader set of parameters under the (randomized) exponential time hypothesis. In our proofs, we use random graphs as gadgets; this is inspired by similar constructions in seminal works on the hardness of approximate counting. In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs. In particular, we prove that identity testing for colorings is hard in the same range of parameters where structure learning is known to be hard, which in turn matches the parameter regime for NP-hardness of the corresponding decision problem.more » « less
-
Intersection graphs of planar geometric objects such as intervals, disks, rectangles and pseudodisks are well-studied. Motivated by various applications, Butman et al. (ACM Trans. Algorithms, 2010) considered algorithmic questions in intersection graphs of $$t$$-intervals. A $$t$$-interval is a union of $$t$$ intervals --- these graphs are also referred to as multiple-interval graphs. Subsequent work by Kammer et al.\ (APPROX-RANDOM 2010) considered intersection graphs of $$t$$-disks (union of $$t$$ disks), and other geometric objects. In this paper we revisit some of these algorithmic questions via more recent developments in computational geometry. For the \emph{minimum-weight dominating set problem} in $$t$$-interval graphs, we obtain a polynomial-time $$O(t \log t)$$-approximation algorithm, improving upon the previously known polynomial-time $t^2$-approximation by Butman et al. In the same class of graphs we show that it is $$\NP$$-hard to obtain a $$(t-1-\epsilon)$$-approximation for any fixed $$t \ge 3$$ and $$\epsilon > 0$$. The approximation ratio for dominating set extends to the intersection graphs of a collection of $$t$$-pseudodisks (nicely intersecting $$t$$-tuples of closed Jordan domains). We obtain an $$\Omega(1/t)$$-approximation for the \emph{maximum-weight independent set} in the intersection graph of $$t$$-pseudodisks in polynomial time. Our results are obtained via simple reductions to existing algorithms by appropriately bounding the union complexity of the objects under consideration.more » « less
-
A Stick graph is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments lie on a “ground line,” a line with slope −1. It is an open question to decide in polynomial time whether a given bipartite graph G with bipartition A∪B has a Stick representation where the vertices in A and B correspond to horizontal and vertical segments, respectively. We prove that G has a Stick representation if and only if there are orderings of A and B such that G’s bipartite adjacency matrix with rows A and columns B excludes three small ‘forbidden’ submatrices. This is similar to characterizations for other classes of bipartite intersection graphs. We present an algorithm to test whether given orderings of A and B permit a Stick representation respecting those orderings, and to find such a representation if it exists. The algorithm runs in time linear in the size of the adjacency matrix. For the case when only the ordering of A is given, we present an O(|A|3|B|3)-time algorithm. When neither ordering is given, we present some partial results about graphs that are, or are not, Stick representable.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-031-52113-3_14
