International Journal of Foundations of Computer Science

The Linear Layout of Graphs problem asks, given a graph $G$ and a positive integer $k$, whether $G$ admits a layout consisting of a linear ordering of its vertices and a partition of its edges into $k$ sets such that the edges in each set meet some special requirements. Specific linear layouts include $k$-Stack Layout, $k$-Queue Layout, $k$-Arch Layout, Mixed $s$-Stack $q$-Queue Layout and others. In this paper, we present a unified approach for kernelization of these linear layout problems parameterized by the vertex cover number $\tau$ of the input graph. The key point underlying our approach is to partition each set of related vertices into two distinct subsets with respect to the specific layouts, which immediately leads to some efficient reduction rules. We first apply this approach to the Mixed $s$-Stack $q$-Queue Layout problem and show that it admits a kernel of size $2^{{𝒪}(\tau )}$, which results in an algorithm running in time ${𝒪}(2^{2^{{𝒪}(\tau )}}+\tau \cdot |V|)$, where $\left|V\right|$ denotes the size of the input graph. Our work does not only confirm the existence of a fixed-parameter tractable algorithm for this problem mentioned by Bhore et al. (J. Graph Algorithms Appl. 2022), but also derives new results for the $k$-Stack Layout problem and for the $k$-Queue Layout problem respectively. We also employ this approach to the Upward $k$-Stack Layout problem and obtain a new result improving that presented by Bhore et al. (GD 2021). Last but not least, we use this approach to the $k$-Arch Layout problem and obtain a similar result.

Many real-world applications arising from social networks, personalized recommendations, and others, require extracting a relatively small but broadly representative portion of massive data sets. Such problems can often be formulated as maximizing a monotone set function with cardinality constraints. In this paper, we consider a streaming model where elements arrive quickly over time, and create an effective, and low-memory algorithm. First, we provide the first single-pass linear-time algorithm, which is a a deterministic algorithm, achieves an approximation ratio of $[\frac{{\gamma }^4}{a(1+\gamma +{\gamma }^2+{\gamma }^3)}-𝜀]$ for any $𝜀\ge 0$ with a query complexity of $\lceil n/a\rceil +a$ and a memory complexity of $O(aklog(k)log(1/𝜀))$, where $a$ is a positive integer and $\gamma$ is the submodularity ratio. However, the algorithm may produce less-than-ideal results. Our next result is to describe a multi-streaming algorithm, which is the first deterministic algorithm to attain an approximation ratio of $1-e^{-\gamma }-𝜀$ with linear query complexity.

The main complexity classes of the Parameterized Intractability Theory are based on weighted Boolean circuit satisfiability problems and organized into a hierarchy so-called W-hierarchy. The W-hierarchy enables fine-grained complexity analyses of parameterized problems that are unlikely to belong to the FPT class. In this paper, we introduce the Th-hierarchy, a natural generalization of the W-hierarchy defined by unweighted threshold circuit satisfiability problems. Investigating the relationship between Th-hierarchy and W-hierarchy, we discuss the complexity of transforming Threshold circuits into Boolean circuits, and observe that sorting networks are powerful tools to handle such transformations. First, we show that these hierarchies collapse at the last level (W[P]$=$Th[P]). After that, we present a time complexity analysis of an AKS sorting network construction, which supports some of our results. Finally, we prove that Th[$t$] $\subseteq$ W[SAT] for every $t\in \mathbb{N}$. As a by-product, our studies suggest that it is relevant to consider a new class based on logarithmic depth circuits in the W-hierarchy.

A set $D\subseteq V$ of a graph $G=(V,E)$ is called a connected power dominating set of $G$ if $G[D]$, the subgraph induced by $D$, is connected and every vertex in the graph can be observed from $D$, following the two observation rules for power system monitoring: Rule $1$: if $v\in D$, then $v$ can observe itself and all its neighbors, and Rule $2$: for an already observed vertex whose all neighbors except one are observed, then the only unobserved neighbor becomes observed as well. Given a graph $G$, Minimum Connected Power Domination is to find a connected power dominating set of minimum cardinality of $G$ and Decide Connected Power Domination is the decision version of Minimum Connected Power Domination. Decide Connected Power Domination is known to be $\mathsf{N}\mathsf{P}$-complete for general graphs. In this paper, we prove that Decide Connected Power Domination remains $\mathsf{N}\mathsf{P}$-complete for star-convex bipartite graphs, perfect elimination bipartite graphs and split graphs. This answers some open problems posed in [B. Brimkov, D. Mikesell and L. Smith, Connected power domination in graphs, J. Comb. Optim. 38(1) (2019) 292–315]. On the positive side, we show that Minimum Connected Power Domination is polynomial-time solvable for chain graphs, a proper subclass of perfect elimination bipartite graph, and for threshold graphs, a proper subclass of split graphs. Further, we show that Minimum Connected Power Domination cannot be approximated within $(1-𝜖)ln\left|V\right|$ for any $𝜖>0$ unless $\mathsf{P}=\mathsf{N}\mathsf{P}$, for bipartite graphs as well as for chordal graphs. Finally, we show that Minimum Connected Power Domination is $\mathsf{APX}$-hard for bounded degree graphs.

We design succinct encodings of series-parallel, block-cactus and 3-leaf power graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood optimally in the RAM model with logarithmic word size. One salient feature of our representation is that it can achieve optimal space even though the exact space lower bound for these graph classes is not known. For these graph classes, we provide succinct data structures with optimal query support for the first time in the literature. For series-parallel multigraphs, our work also extends the works of Uno et al. (Disc. Math. Alg. and Appl., 2013) and Blelloch and Farzan (CPM, 2010) to produce optimal bounds.

Given a set ${𝒫}$ of $h$ pairwise disjoint convex polygonal obstacles in the plane, defined with $n$ vertices, we preprocess ${𝒫}$ and compute one routing table at each vertex in a subset of vertices of ${𝒫}$. For routing a packet from any vertex $s\in {𝒫}$ to any vertex $t\in {𝒫}$, our scheme computes a routing path with a multiplicative stretch $1+𝜖$ and an additive stretch $2k\ell$, by consulting routing tables at only a subset of vertices along that path. Here, $k$ is the number of obstacles of ${𝒫}$ the routing path intersects, and $\ell$ depends on the geometry of obstacles in ${𝒫}$. During the preprocessing phase, we construct routing tables of size $O(n+\frac{h^3}{{𝜖}^2}\text{polylog}(\frac{h}{𝜖}))$ in $O(n+\frac{h^3}{{𝜖}^2}\text{polylog}(\frac{h}{𝜖}))$ time, where $𝜖<1$ is an input parameter.

In our modern societies, a certain number of people do not own a car, by choice or by obligation. For some trips, there is no or few alternatives to the car. One way to make these trips possible for these people is to be transported by others who have already planned their trips. We propose to model this problem using as path-finding problem in a list edge-colored graph. This problem is a generalization of the $s-t$-path problem, studied by Böhmová et al. We consider two optimization functions: minimizing the number of color changes and minimizing the number of colors. We study for the previous problems, the classic complexity (polynomial-case, NP-completeness, hardness of approximation) and parameter complexity (W[2]-hardness) even in restricted cases. We also propose a lower bound for exact algorithm. On the positive side we provide a polynomial-time approximation algorithm and a FPT algorithm.

Correlation clustering problem (CorCP) is a classical clustering problem, which clusters data based on the similarity of data set, and has many applications in interaction networks, cross-lingual link detection, and communication networks, etc. In this paper, we study a practical generalization of the CorCP, called the capacitated correlation clustering problem (the capacitated CorCP), by constructing a labeled complete graph. On this labeled complete graph, each vertex represents a piece of data. If two pieces of data are similar, then the edge between the corresponding vertices is marked by a positive label +. Otherwise, this edge is marked by a negative label -. The objective of the capacitated CorCP is to group some similar data sets into one cluster as far as possible, while satisfying the cluster capacity constraint. To achieve this objective, we shall partition the vertex set of the labeled complete graph into several clusters, each cluster’s size subjecting to an upper bound, so as to minimize the number of disagreements. Here the number of disagreements is defined as the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. Different with the previous algorithm in [18], which subjects to the constraint on the cluster size by a penalty measure, we design an algorithm for the capacitated CorCP to directly output a feasible solution by iteratively constructing clusters based on a preset threshold. Through carefully setting the threshold and sophisticatedly analyzing, our algorithm is proved to have an improved approximation ratio of 5.37. In addition, we also conduct a series of numerical experiments to demonstrate the effectiveness of our algorithm.