Department of Computer Science and Engineering

Indian Institute of Technology Palakkad&nbsp;(IIT Palakkad or IIT PKD) is a public autonomous&nbsp;engineering&nbsp;and&nbsp;research&nbsp;institute located in&nbsp;Palakkad,&nbsp;Kerala. It was&nbsp;one of the five new&nbsp;IITs&nbsp;proposed in the&nbsp;2014 Union budget of India. The campus was inaugurated on 3 August 2015. The institute has 94 faculty, 978 students, and 63 non-teaching staffs.

IT Palakkad currently offers four-year Bachelor of Technology (B.Tech) and two years MS programmes in 8 different engineering disciplines including&nbsp;Computer Science, Electrical, Mechanical, Civil among others.

&nbsp;

IIT Palakkad

The anti-Ramsey number ar(G,H) with input graph G and pattern graph H, is the maximum positive integer k such that there exists an edge coloring of G using k colors, in which there are no rainbow subgraphs isomorphic to H in G. (H is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erdős et al. in 1973. Thereafter, several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph K1,t (for t≥3) purely from an algorithmic point of view. For a graph G and an integer q≥2, an edge q-coloring of G is an assignment of colors to edges of G, such that the edges incident on a vertex span at most q distinct colors. The maximum edge q-coloring problem seeks to maximize the number of colors in an edge q-coloring of the graph G. Note that the optimum value of the edge q-coloring problem of G equals ar(G,K1,q+1). Here, we study ar(G,K1,t), the anti-Ramsey number of stars, for each fixed integer t≥3, both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for ar(G,K1,q+1), in terms of number of vertices and the minimum degree of G. The second one improves this result for the case of triangle-free input graphs. Our third main result presents an upper bound for ar(G,K1,q+1) in terms of |E(G≤(q−1))|, which is a frequently used lower bound for ar(G,K1,q+1) and maximum edge q-coloring in the literature. All our results have algorithmic consequences. © 2024 Elsevier B.V.

World University root node

Discrete Mathematics

New bounds on the anti-Ramsey numbers of star graphs via maximum edge q-coloring

A domatic (resp. total domatic) k-coloring of a graph G is an assignment of k colors to the vertices of G such that each vertex contains vertices of all k colors in its closed neighborhood (resp. open neighborhood). The domatic (resp. total domatic) number of G, denoted d(G) (resp. dt(G)), is the maximum k for which G has a domatic (resp. total domatic) k-coloring. In this paper, we show that for two non-trivial graphs G and H, the domatic and total domatic numbers of their Cartesian product G□ H is bounded above by max { | V(G) | , | V(H) | } and below by max { d(G) , d(H) } . Both these bounds are tight for an infinite family of graphs. Further, we show that if H is bipartite, then dt(G□ H) is bounded below by 2 min { dt(G) , dt(H) } and d(G□ H) is bounded below by 2 min { d(G) , dt(H) } . As a consequences, we get new bounds for the domatic and total domatic number of hypercubes and Hamming graphs of certain dimensions, and exact values for some n-dimensional tori which turns out to be a generalization of a result due to Gravier from 2002. © 2023, The Author(s), under exclusive licence to Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia.

Bulletin of the Malaysian Mathematical Sciences Society

On Domatic and Total Domatic Numbers of Cartesian Products of Graphs

For a collection F of graphs, the F-CONTRACTION problem takes a graph G and an integer k as input and decides if G can be modified to some graph in F using at most k edge contractions. The F-CONTRACTION problem is NP-Complete for several graph classes F. Heggernes et al. (2014) [4] initiated the study of F-CONTRACTION in the realm of parameterized complexity. They showed that it is FPT if F is the set of all trees or the set of all paths. In this paper, we study F-CONTRACTION where F is the set of all cactus graphs and show that we can solve it in 2O(k)⋅|V(G)|O(1) time. © 2023 Elsevier B.V.

Theoretical Computer Science

A single exponential-time FPT algorithm for cactus contraction

In SDN-based networks, contextual understanding of network behaviour and safe execution of operational decisions are important as part of the network management process. Digital Twin Network (DTN) is a promising concept which creates a virtual twin of a live SDN-based network to monitor the network from different angles with various granularities and enables it to verify an operational change without disturbing the live one. However, modelling the arbitrary decisions by an SDN Controller to form a DTN and managing the contextual information in a DTN are challenging tasks in various aspects. This paper proposes a data representation based DTN architecture integrating Knowledge Graph (KG) for data modelling and storage and Template as the context description approach. The combination of KG and Template can make the DTN management scalable with the flexibility of defining the contextual information with the relationships between network entities. It also enables efficient querying of the data storage and provides the reusability of functions and data storage for the DTN applications development. The proposed DTN architecture was implemented using an ONOS-based SDN Controller and Neo4j-based KG with built-in DTN applications for practical use. The PoC implementation exhibited short query response time and high query throughput in reading from and updating a KG, though the initial creation of a KG incurs a considerable delay which increases with its size. © 2013 IEEE.

IEEE Access

Building a Digital Twin Network of SDN Using Knowledge Graphs

An edge-colored graph is said to be balanced if it has an equal number of edges of each color. Given a graph G whose edges are colored using two colors and a positive integer k, the objective in the Edge Balanced Connected Subgraph problem is to determine if G has a balanced connected subgraph containing at least k edges. We first show that this problem is NP -complete and remains so even if the solution is required to be a tree or a path. Then, we focus on the parameterized complexity of Edge Balanced Connected Subgraph and its variants (where the balanced subgraph is required to be a path/tree) with respect to k as the parameter. Towards this, we show that if a graph has a balanced connected subgraph/tree/path of size at least k, then it has one of size at least k and at most f(k) where f is a linear function. We use this result combined with dynamic programming algorithms based on color coding and representative sets to show that Edge Balanced Connected Subgraph and its variants are FPT. Further, using polynomial-time reductions to the Multilinear Monomial Detection problem, we give faster randomized FPT algorithms for the problems. In order to describe these reductions, we define a combinatorial object called relaxed-subgraph. We define this object in such a way that balanced connected subgraphs, trees and paths are relaxed-subgraphs with certain properties. This object is defined in the spirit of branching walks known for the Steiner Tree problem and may be of independent interest. © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Balanced Substructures in Bicolored Graphs

A bipartite graph is called a biclique if it is a complete bipartite graph and a biclique is called a balanced biclique if it has equal number of vertices in both parts of its bipartition. In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objective is to determine whether one can contract at most k edges in G to obtain a biclique and a balanced biclique, respectively. We first prove that these problems are NP-complete even when the input graph is bipartite. Next, we study the parameterized complexity of these problems and show that they admit single exponentialtime FPT algorithms when parameterized by the number k of edge contractions. Then, we show that Balanced Biclique Contraction admits a quadratic vertex kernel while Biclique Contraction does not admit any polynomial compression (or kernel) unless NP ? coNP/poly. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

Leibniz International Proceedings in Informatics, LIPIcs

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction

We show that every simple planar near-triangulation with minimum degree at least three contains two disjoint total dominating sets. The class includes all simple planar triangulations other than the triangle. This affirms a conjecture of Goddard and Henning. © 2023 Wiley Periodicals LLC.

Journal of Graph Theory

Disjoint total dominating sets in near-triangulations

B0 -VPG graphs are intersection graphs of axis-parallel line segments in the plane. We show that all AT-free outerplanar graphs are B0 -VPG. In the course of the argument, we show that any AT-free outerplanar graph can be identified as an induced subgraph of a 2-connected outerplanar graph whose weak dual is a path. Our B0 -VPG drawing procedure works for such graphs and has the potential to be extended to larger classes of outerplanar graphs. © 2022, Springer Nature Switzerland AG.

B0 -VPG Representation of AT-free Outerplanar Graphs

Arrayed Waveguide Grating Router (AWGR) based optical networks are emerging as a promising solution for handling modern data centers due to their wide bandwidth, scalability, high data rates, and lower latency. However, link failures in AWGR based optical networks can significantly impact the network performance and lead to the loss of reachability due to the rigid, passive wavelength routing. In this paper, we present ResiConnect, a scalable, and resilient optical network architecture. ResiConnect is a 3-stage Clos network of AWGR, space switches, and AWGR (ASA) which is managed by a centralized controller. ResiConnect introduces an alternative path to redirect the affected traffic by vertically connecting transmitters, and incorporates an active link fault detection and the failover traffic steering. The evaluation results on various performance metrics confirm that ResiConnect is 1) resilient and scalable against multiple link faults, 2) efficient in detecting any link fault with minimum resource overhead, and 3) efficient in handling uneven traffic demand during link failure. © 2022 IEICE.