A multipacking in an undirected graph G = (V, E) is a set M ⊆ V such that for every vertex v ∈ V and for every integer r ≥ 1, the ball of radius r around v contains at most r vertices of M, that is, there are at most r vertices in M at a distance at most r from v in G. The Multipacking problem asks whether a graph contains a multipacking of size at least k. For more than a decade, it remained an open question whether the Multipacking problem is NP-complete or solvable in polynomial time, although the problem is known to be polynomial-time solvable for certain graph classes (e.g., strongly chordal graphs, grids, etc). Foucaud, Gras, Perez, and Sikora [Foucaud et al., 2021] [Algorithmica 2021] made a step towards solving the open question by showing that the Multipacking problem is NP-complete for directed graphs and W[1]-hard when parameterized by the solution size. In this paper, we prove that the Multipacking problem is NP-complete on undirected graphs, which answers the open question. Moreover, the problem is W[2]-hard on undirected graphs when parameterized by the solution size. Furthermore, we show that the problem is NP-complete and W[2]-hard (parameterized by solution size) on chordal, bipartite, and claw-free graphs, and remains NP-complete on regular and CONV graphs (intersection graphs of convex sets in the plane). Additionally, the problem is NP-complete and W[2]-hard (parameterized by the solution size) on chordal ∩ 1/2-hyperbolic graphs, which is a superclass of strongly chordal graphs on which the problem is polynomial-time solvable. On the positive side, we present an exact exponential-time algorithm for the Multipacking problem on general graphs that breaks the 2ⁿ barrier, with running time O^*(1.58ⁿ), where n is the number of vertices.

We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set $S$ of vertices of a graph $G$ is a \textit{geodetic set} if every vertex of $G$ lies in a shortest path between some pair of vertices of $S$. The \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality of a given graph. We show that \textsc{Minimum Geodetic Set} is fixed parameter tractable for chordal graphs when parameterized by its \emph{tree-width} (which equals its clique number). This implies a polynomial-time algorithm for $k$-trees, for fixed $k$. Then, we show that \textsc{Minimum Geodetic Set} is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012), who showed that \textsc{Minimum Geodetic Set} is polynomial-time solvable on proper interval graphs. As interval graphs are very constrained, to prove the latter result, we design a rather sophisticated reduction technique to work around their inherent linear structure.

A terrain is an $x$-monotone polygon whose lower boundary is a single line segment. We present an algorithm to find in a terrain a triangle of largest area in $O(nlog n)$ time, where $n$ is the number of vertices defining the terrain. The best previous algorithm for this problem has a running time of $O(n^2)$.

An ( n , m ) -graph is characterized by n types of arcs and m types of edges. A homomorphism of an ( n , m ) -graph G to an ( n , m ) -graph H , is a vertex mapping that preserves adjacency, direction, and type. The ( n , m ) -chromatic number of G , denoted by χ n , m ( G ) , is the minimum value of | V ( H ) | such that there exists a homomorphism of G to H . The theory of homomorphisms of ( n , m ) -graphs have connections with graph theoretic concepts like harmonious coloring, nowhere-zero flows; with other mathematical topics like binary predicate logic , Coxeter groups; and has application to the Query Evaluation Problem (QEP) in graph database. In this article, we show that the arboricity of G is bounded by a function of χ n , m ( G ) but not the other way around. Additionally, we show that the acyclic chromatic number of G is bounded by a function of χ n , m ( G ) , a result already known in the reverse direction. Furthermore, we prove that the ( n , m ) -chromatic number for the family of graphs with maximum average degree less than 2 + 2 4 ( 2 n + m ) − 1 , including the subfamily of planar graphs with girth at least 8 ( 2 n + m ) , equals 2 ( 2 n + m ) + 1 . This improves upon previous findings, which proved the ( n , m ) -chromatic number for planar graphs with girth at least 10 ( 2 n + m ) − 4 is 2 ( 2 n + m ) + 1 . It is established that the ( n , m ) -chromatic number for the family T 2 of partial 2-trees is both bounded below and above by quadratic functions of ( 2 n + m ) , with the lower bound being tight when ( 2 n + m ) = 2 . We prove 14 ≤ χ ( 0 , 3 ) ( T 2 ) ≤ 15 and 14 ≤ χ ( 1 , 1 ) ( T 2 ) ≤ 21 which improves both known lower bounds and the former upper bound. Moreover, for the latter upper bound, to the best of our knowledge we provide the first theoretical proof.

A path is isometric if it is a shortest path between its endpoints. In this article, we consider the graph covering problem Isometric Path Cover, where we want to cover all the vertices of the graph using a minimum-size set of isometric paths. Although this problem has been considered from a structural point of view (in particular, regarding applications to pursuit-evasion games), it is little studied from the algorithmic perspective. We consider Isometric Path Cover on chordal graphs, and show that the problem is NP-hard for this class. On the positive side, for chordal graphs, we design a 4-approximation algorithm and an FPT algorithm for the parameter solution size. The approximation algorithm is based on a reduction to the classic path covering problem on a suitable directed acyclic graph obtained from a breadth first search traversal of the graph. The approximation ratio of our algorithm is 3 for interval graphs and 2 for proper interval graphs. Moreover, we extend the analysis of our approximation algorithm to k-chordal graphs (graphs whose induced cycles have length at most k) by showing that it has an approximation ratio of k+7 for such graphs, and to graphs of treelength at most 𝓁, where the approximation ratio is at most 6𝓁+2.

We present a linear time algorithm for the weighted k -center problem on trees for fixed k . This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O ( n log ⁡ n ) by Wang et al. (2018) [20] . Whether an O ( n ) time algorithm exists for arbitrary k is still open.

A set $S$ of vertices of a graph $G$ is a \emph{geodetic set} if every vertex of $G$ lies in a shortest path between some pair of vertices of $S$. The \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality of a given graph. A \emph{grid embedding} of a graph is a set of points in two dimensions with integer coordinates such that each point in the set represents a vertex of the graph and, for each edge, the points corresponding to its endpoints are at Euclidean distance~$1$. A graph is a \emph{partial grid} if it has a grid embedding. In this paper, we first prove that \textsc{Minimum Geodetic Set} remains NP-hard even for subcubic partial grids of arbitrary girth. This jointly strengthens three existing hardness results: for bipartite graphs (Dourado et al., Discrete. Math, 2010), subcubic graphs (Bueno et al., Inf. Process. Lett., 2018)~\cite{bueno2018}, and planar graphs (Chakraborty et al., CALDAM, 2020). The \emph{area} of an internal face is the number of integer points lying on the boundary or interior of the face. A graph is a \emph{solid grid} if it has a grid embedding such that all interior faces have area exactly four. To complement the above hardness result, we design a linear-time algorithm for \textsc{Minimum Geodetic Set} on solid grids, improving on a $3$-approximation algorithm by Chakraborty et al. (CALDAM, 2020). Our results hold for \textsc{Edge Geodetic Set} as well. A set $S$ of vertices of a graph $G$ is a \emph{geodetic set} if every edge of $G$ lies in a shortest path between some pair of vertices of $S$. The \textsc{Minimum Edge Geodetic Set (MEGS)} problem is to find an edge geodetic set with minimum cardinality of a given graph. As corollaries, we obtain that \textsc{MEGS} remains NP-hard on partial grids and is linear-time solvable on solid grids.

Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoretical guarantee on its quality. The other one considers placement as a graph-embedding problem and designs approximation algorithms with provable bounds on the quality of the solution. In this article, we aim at unifying the above two directions. First, we extend the existing approximation algorithms for graph embedding in 1D and 2D grid to those for hypergraphs, which typically model circuits to be placed on a FPGA. We prove an approximation bound of O ( d √log n log log n ) for 1D, that is, linear arrangement and O ( d log n log log n ) for the 2D grid, where d is the maximum degree of hyperedges and n , the number of vertices in the hypergraph. Next, we propose an efficient method based on linear arrangement of the CLBs and the notion of space-filling curves for placing the configurable logic blocks (CLBs) of a netlist on island-style FPGAs with an approximation guarantee of O ( 4 √log n √ kd log log n ), where k is the number of nets. For the set of FPGA placement benchmarks, the running time is near linear in the number of CLBs thus allowing for scalability towards large circuits. We obtained a 33× speed-up, on average, with only 1.31× degradation in the quality of the solution compared to that produced by the popular FPGA tool VPR, thereby demonstrating the suitability of this very fast method for FPGA placement, with a provable performance guarantee.

In this paper, we propose a placement method for island-style FPGAs, based on recursive bi-partitioning followed by application of space-filling curves. Experimental results of our method show 55% improvement in cost, when compared to random initial placement of the popular tool VPR. The solutions thus obtained require 44.5% fewer moves during final iterative refinement by ultra-low temperature simulated annealing, whereas the quality of solution is on the average 0.1% better. This establishes the utility of the method for fast reconfiguration of FPGA based co-processors.

New techniques are presented for routing straight channels, L-channels, switchboxes, and staircase channels in a two-layer Manhattan-diagonal (MD) model with tracks in horizontal, vertical, and ± 45° directions. First, an O ( l.d ) time algorithm is presented for routing a straight channel of length l and density d with no cyclic vertical constraints . It is shown that the number of tracks h used by the algorithm for routing multiterminal nets satisfies d ≤ h ≤ ( d + 1). Second, an output-sensitive algorithm is reported that can route a channel with cyclic vertical constraints in O ( l.h ) time using h tracks, allowing overlapping of wire segments in two layers. Next, the routing problem for a multiterminal L-channel of length l and height h is solved by an O ( l.h ) time algorithm. If no cyclic vertical constraints exist, its time complexity reduces to O ( l.d ) where d is the density of the L-channel. Finally, the switchbox routing problem in the MD model is solved elegantly. These techniques, easily extendible to the routing of staircase channels, yield efficient solutions to detailed routing in general floorplans. Experimental results on benchmarks show significantly low via count and reduced wire length, thus establishing the superiority of MD routing to classical strategies. The proposed algorithms are also potentially useful for general non-Manhattan area routing and multichip modules (MCMs).

A new technique of synthesizing totally symmetric Boolean functions is presented that achieves complete robust path-delay fault testability. We show that every consecutive symmetric function can be expressed as a logical composition (e.g., AND, NOR) of two unate symmetric functions, and the resulting composite circuit can be made robustly path-delay fault testable, if the constituent unate functions are synthesized as two-level irredundant circuits. Nonconsecutive symmetric functions can also be synthesized by decomposing them into a set of consecutive symmetric functions. The circuit cost of the proposed design can further be reduced by a novel algebraic factorization technique based on some combinatorial clues. The overall synthesis guarantees complete robust path-delay fault testability, and can be completed in linear time. The results shows that the proposed method ensures a significant reduction in hardware, as well as in the number of paths, which in turn, reduces testing time, as compared to those of the best-known earlier methods.