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

World University root node

US Patent App. 17/492,264

Communication entity and a method for transmitting a video data stream

B0-VPG graphs are intersection graphs of axis-parallel line segments in the plane. Cohen et al. (Order 33(1), 39–49, 2016) pose the question of characterizing B0-VPG permutation graphs. We respond here by characterizing B0-VPG cocomparability graphs. This helps us show that a simple necessary condition in fact characterizes B0-VPG permutation graphs. The characterization also leads to a polynomial time recognition algorithm and its proof gives us a B0-VPG drawing algorithm for the class of B0-VPG cocomparability graphs. Our drawing algorithm starts by fixing any one of the many posets P whose cocomparability graph is the input graph G. On the set of axis-parallel line segments in the plane, we define a binary relation “≺2” as p ≺2q if and only if they are non-intersecting and the bottom-left endpoint of p precedes the top-right endpoint of q in the product order on ℝ2. The reflexive closure ≼2 of the relation ≺2 restricted to the line segments of our drawing turns out to be a partial order isomorphic to the poset P. © 2021, The Author(s), under exclusive licence to Springer Nature B.V.

Order

Characterization of B0-VPG Cocomparability Graphs and a 2D Visualization of their Posets

arXiv preprint arXiv:2201.

Eternal vertex cover number of maximal outerplanar graphs

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Bounded Indistinguishability for Simple Sources

Given a directed graph G and a positive integer k, the Arc Disjoint r-Cycle Packing problem asks whether G has k arc-disjoint r-cycles. We show that, for each integer r ≥ 3, Arc Disjoint r-Cycle Packing is NP-complete on oriented graphs with girth r. When r is even, the same result holds even when the input class is further restricted to be bipartite. On the positive side, focusing on r = 4 in oriented graphs, we study the complexity of the problem with respect to two parameterizations: solution size and vertex cover size. For the former, we give a cubic kernel with quadratic number of vertices. This is smaller than the compression size guaranteed by a reduction to the well-known 4-Set Packing. For the latter, we show fixed-parameter tractability using an unapparent integer linear programming formulation of an equivalent problem. © Jasine Babu, R. Krithika, and Deepak Rajendraprasad; licensed under Creative Commons License CC-BY 4.0.

Leibniz International Proceedings in Informatics, LIPIcs

Packing Arc-Disjoint 4-Cycles in Oriented Graphs

Almost full rank matrices arising from transitive tournaments

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.

Conference on Algorithms and Discrete Applied Mathematics

B0-VPG Representation of AT-free Outerplanar Graphs

For a positive integer $$\ell \ge 3$$, the $$C:\ell $$ -Contractibility problem takes as input an undirected simple graph G and determines whether G can be transformed into a graph isomorphic to $$C:\ell $$ (the induced cycle on $$\ell $$ vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed that $$C:4$$ -Contractibility is $$\textsf{NP}$$ -complete in general graphs. It is easy to verify that that $$C:3$$ -Contractibility is polynomial-time solvable. Dabrowski and Paulusma [IPL 2017] showed that $$C:{\ell }$$ -Contractibility is $$\textsf{NP}$$ -complete on bipartite graphs for $$\ell = 6$$ and posed as open problems the status of $$C:{\ell }$$ -Contractibility when $$\ell $$ is 4 or 5. In this paper, we show that both $$C:5$$ -Contractibility and $$C:4$$ -Contractibility are $$\textsf{NP}$$ -complete on bipartite graphs. © 2022, Springer Nature Switzerland AG.

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

The Complexity of Contracting Bipartite Graphs into Small Cycles

A mixed multigraph is a multigraph which may contain both undirected and directed edges. An orientation of a mixed multigraph G is an assignment of exactly one direction to each undirected edge of G. A mixed multigraph G can be oriented to a strongly connected digraph if and only if G is bridgeless and strongly connected [Boesch and Tindell, Am. Math. Mon., 1980]. For each r∈N, let f(r) denote the smallest number such that any strongly connected bridgeless mixed multigraph with radius r can be oriented to a digraph of radius at most f(r). We improve the current best upper bound of 4r2+4r on f(r) [Chung, Garey and Tarjan, Networks, 1985] to 1.5r2+r+1. Our upper bound is tight upto a multiplicative factor of 1.5 since, ∀r∈N, there exists an undirected bridgeless graph of radius r such that every orientation of it has radius at least r2+r [Chvátal and Thomassen, J. Comb. Theory. Ser. B., 1978]. We prove a marginally better lower bound, f(r)≥r2+3r+1, for mixed multigraphs. While this marginal improvement does not help with asymptotic estimates, it clears a natural suspicion that, like undirected graphs, f(r) may be equal to r2+r even for mixed multigraphs. En route, we show that if each edge of G lies in a cycle of length at most η, then the oriented radius of G is at most 1.5rη. All our proofs are constructive and lend themselves to polynomial time algorithms.

Improved Bounds for the Oriented Radius of Mixed Multigraphs

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 2O(klogk)nO(1)<math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mi>k</mi><mi>log</mi><mo>⁡</mo><mi>k</mi><mo stretchy="false">)</mo></mrow></msup><msup><mi>n</mi><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup></math>-time algorithm and admits a kernel with O(k)<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></math>&nbsp;vertices. Then, we show that ATT too has a kernel with O(k)<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></math>&nbsp;vertices and can be solved in 2O(k)nO(1)<math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></mrow></msup><msup><mi>n</mi><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup></math>&nbsp;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)<math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mi>o</mi><mo stretchy="false">(</mo><msqrt><mi>n</mi></msqrt><mo stretchy="false">)</mo></mrow></msup><msup><mi>n</mi><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup></math>&nbsp;time under the exponential-time hypothesis.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 2O(klogk)nO(1)<math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mi>k</mi><mi>log</mi><mo>⁡</mo><mi>k</mi><mo stretchy="false">)</mo></mrow></msup><msup><mi>n</mi><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup></math>-time algorithm and admits a kernel with O(k)<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></math>&nbsp;vertices. Then, we show that ATT too has a kernel with O(k)<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></math>&nbsp;vertices and can be solved in 2O(k)nO(1)<math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></mrow></msup><msup><mi>n</mi><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup></math>&nbsp;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)<math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mi>o</mi><mo stretchy="false">(</mo><msqrt><mi>n</mi></msqrt><mo stretchy="false">)</mo></mrow></msup><msup><mi>n</mi><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup></math>&nbsp;time under the exponential-time hypothesis.