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

An orientation of an undirected graph G is an assignment of exactly one direction to each edge of G. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest. The n-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy (1989). The n-star graph Sn consists of n! vertices, each labelled with a distinct permutation of [n]. Two vertices are adjacent if their labels differ exactly in the first and one other position. Sn is an (n−1)-regular, vertex-transitive graph with diameter ⌊3(n−1)∕2⌋. Orientations of Sn, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi (1993) and Fujita (2013). Fujita showed that the (directed) diameter of this unidirectional star graph Sn⃗ is at most ⌈5n∕2⌉+2. In this paper, we propose a new distributed routing algorithm for the same Sn⃗ analysed by Fujita, which routes a packet from any node s to any node t at an undirected distance d from s using at most min{4d+4,2n+4} hops. This shows that the (directed) diameter of Sn⃗ is at most 2n+4. We also show that the diameter of Sn⃗ is at least 2n when n≥7, thereby showing that our upper bound is tight up to an additive factor. © 2021 Elsevier B.V.

World University root node

Fulltext

Discrete Applied Mathematics

Oriented diameter of star graphs

We introduce and study a d-dimensional generalization of graph Hamiltonian cycles. These are the Hamiltonian d-dimensional cycles in Knd (the complete simplicial d-complex over a vertex set of size n). Hamiltonian d-cycles are the simple d-cycles of a complete rank, or, equivalently, of size 1+(n−1d). The discussion is restricted to the fields F2 and Q. For d=2, we characterize the n's for which Hamiltonian 2-cycles exist. For d=3 it is shown that Hamiltonian 3-cycles exist for infinitely many n's. In general, it is shown that there always exist simple d-cycles of size (n−1d)−O(nd−3). All the above results are constructive. Our approach naturally extends to (and in fact, involves) d-fillings, generalizing the notion of T-joins in graphs. Given a (d−1)-cycle Zd−1∈Knd, F is its d-filling if ∂F=Zd−1. We call a d-filling Hamiltonian if it is acyclic and of a complete rank, or, equivalently, is of size (n−1d). If a Hamiltonian d-cycle Z over F2 contains a d-simplex σ, then Z∖σ is a Hamiltonian d-filling of ∂σ (a closely related fact is also true for cycles over Q). Thus, the two notions are closely related. Most of the above results about Hamiltonian d-cycles hold for Hamiltonian d-fillings as well. © 2021 Elsevier Inc.

Journal of Combinatorial Theory. Series B

Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes

An orientation of an undirected graph G is an assignment of exactly one direction to each edge of G. The oriented diameter of a graph G is the smallest diameter among all the orientations of G. The maximum oriented diameter of a family of graphs ℱ is the maximum oriented diameter among all the graphs in ℱ. Chvátal and Thomassen [JCTB, 1978] gave a lower bound of [Figure presented] and an upper bound of 2d2+2d for the maximum oriented diameter of the family of 2-edge connected graphs of diameter d. We improve this upper bound to 1.373d2+6.971d−1, which outperforms the former upper bound for all values of d greater than or equal to 8. For the family of 2-edge connected graphs of diameter 3, Kwok, Liu and West [JCTB, 2010] obtained improved lower and upper bounds of 9 and 11 respectively. For the family of 2-edge connected graphs of diameter 4, the bounds provided by Chvátal and Thomassen are 12 and 40 and no better bounds were known. By extending the method we used for diameter d graphs, along with an asymmetric extension of a technique used by Chvátal and Thomassen, we have improved this upper bound to 21.1 © 2021 Elsevier B.V.

An improvement to Chvátal and Thomassen's upper bound for oriented diameter

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these problems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles in Tournaments (ATT), respectively. Although the maximization version of ACT can be seen as the dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results seem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we show that the problem of determining if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete. Next, we prove that ACT is fixed-parameter tractable via a 2 O(klogk)nO(1)-time algorithm and admits a kernel with O(k) vertices. Then, we show that ATT too has a kernel with O(k) vertices and can be solved in 2 O(k)nO(1) time. Afterwards, we describe polynomial-time algorithms for ACT and ATT when the input tournament has a feedback arc set that is a matching. We also prove that ACT and ATT cannot be solved in 2o(n)nO(1) time under the exponential-time hypothesis. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.

Algorithmica

Packing Arc-Disjoint Cycles in Tournaments

The eternal vertex cover (EVC) problem is to compute the minimum number of guards to be placed on the vertices of a graph so that any sequence of attacks on its edges can be defended by dynamically reconfiguring the guards. The problem is NP-hard in general and polynomial time algorithms are unknown even for simple graph classes like cactus graphs and bipartite graphs. A major difficulty is that only few lower bounds, other than the trivial lower bound of vertex cover, is known in general and the known bounds are too weak to yield useful results even for the graph classes mentioned above. We introduce the notion of substructure property in the context of the EVC problem and derive a new lower bounding technique for the problem based on the property. We apply the technique to cactus graphs and chordal graphs and obtain new algorithms for solving the eternal vertex cover problem in linear time for cactus graphs and quadratic time for a family of graphs that includes all chordal graphs and cactus graphs. © 2021 Elsevier B.V.

Theoretical Computer Science

A substructure based lower bound for eternal vertex cover number

An orientation of an undirected graph G is an assignment of exactly one direction to each edge of G. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest.The n-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy [IEEE Trans. on Computers (1989)]. The n-star graph Sn consists of n! vertices, each labelled with a distinct permutation of [n]. Two vertices are adjacent if their labels differ exactly in the first and one other position. Sn is an (n−1)-regular, vertex-transitive graph with diameter ⌊3(n−1)/2⌋. Orientations of Sn, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi [Information Processing Letters (1993)] and Fujita [The First International Symposium on Computing and Networking (CANDAR 2013)]. Fujita showed that the (directed) diameter of this unidirectional star graph Sn−→ is at most ⌈5n/2⌉+2.In this paper, we propose a new distributed routing algorithm for the same Sn−→ analysed by Fujita, which routes a packet from any node s to any node t at an undirected distance d from s using at most min{4d+4,2n+4} hops. This shows that the (directed) diameter of Sn−→ is at most 2n+4. We also show that the diameter of Sn−→ is at least 2n when n≥7, thereby showing that our upper bound is tight up to an additive factor.

Algorithms and Discrete Applied Mathematics

Oriented Diameter of Star Graphs

Memory-safety attacks have been one of the most critical threats against computing systems. Although a wide-range of defense techniques have been developed against these attacks, the existing mitigation strategies have several limitations. In particular, most of the existing mitigation approaches are based on aborting or restarting the victim program when a memory-safety attack is detected, thus making the system unavailable. This might not be acceptable in systems with stringent timing constraints, such as cyber-physical systems (CPS), since the system unavailability leaves the control system in an unsafe state. To address this problem, we propose CIMA – a resilient mitigation technique that prevents invalid memory accesses at runtime. CIMA manipulates the compiler-generated control-flow graph to automatically detect and bypass unsafe memory accesses at runtime, thereby mitigating memory-safety attacks along the process. An appealing feature of CIMA is that it significantly improves system availability and resilience of the CPS even under the presence of memory-safety attacks. To this end, we design our experimental setup based on a realistic Secure Water Treatment (SWaT) and Secure Urban Transportation System (SecUTS) testbeds and evaluate the effectiveness and the efficiency of our approach. The experimental results reveal that CIMA handles memory-safety attacks effectively while meeting the real-time constraints and physical-state resiliency of the CPS under test. Using CIMA, we have also discovered a memory-safety vulnerability in the firmware of programmable logic controllers and a CVE ID has already been assigned for it. © 2020 Elsevier Ltd