Geevarghese Philip

Geevarghese Philip

orcid

Research Focus & Metrics

Academic Career Length

8Years (2019-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 February 2022 in Artificial Intelligence
Verified
Journal Article
Closed access
JBJulien Baste
Julien Baste
MFMichael R. Fellows
Michael R. Fellows
LJLars Jaffke
Lars Jaffke
TMTomáš Masařík
Tomáš Masařík
MOMateus de Oliveira Oliveira
Mateus de Oliveira Oliveira
Frances  RosamondFrances Rosamond
Frances Rosamond

27 November 2019 in Algorithms
Verified
Journal Article
Open access
PDF file
JBJulien Baste
Julien Baste
LJLars Jaffke
Lars Jaffke
TMTomáš Masařík
Tomáš Masařík
GPGeevarghese Philip
Geevarghese Philip
GRGünter Rote
Günter Rote
In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in k + r for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of ‘base’ solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest.

4 June 2019 in Algorithmica
Verified
Journal Article
Closed access
PDF file
GPGeevarghese Philip
Geevarghese Philip
VRVarun Rajan
Varun Rajan
SSSaket Saurabh
Saket Saurabh
PTPrafullkumar Tale
Prafullkumar Tale

15 March 2024 in Algorithmica
Verified
Journal Article
Open access
PDF file
FFFedor V. Fomin
Fedor V. Fomin
PGPetr A. Golovach
Petr A. Golovach
LJLars Jaffke
Lars Jaffke
GPGeevarghese Philip
Geevarghese Philip
DSDanil Sagunov
Danil Sagunov
We initiate the study of theDiverse Pair of (Maximum/ Perfect) Matchingsproblems which given a graphGand an integerk, ask whetherGhas two (maximum/perfect) matchings whose symmetric difference is at leastk.Diverse Pair of Matchings(asking for two not necessarily maximum or perfect matchings) is $$\textsf{NP}$$NP -complete on general graphs ifkis part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show thatDiverse Pair of Maximum Matchingsis $$\textsf{FPT}$$FPT parameterized byk. We round off the work by showing thatDiverse Pair of Matchingshas a kernel on $${\mathcal {O}}(k^2)$$O(k2) vertices.

15 April 2023 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
FFFedor V. Fomin
Fedor V. Fomin
PGPetr A. Golovach
Petr A. Golovach
FPFahad Panolan
Fahad Panolan
GPGeevarghese Philip
Geevarghese Philip
SSSaket Saurabh
Saket Saurabh
We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid $$M$$ M , a weight function $$\omega :E(M)\rightarrow \mathbb {N} $$ ω : E ( M ) → N , and integers $$k\ge 1, d\ge 1$$ k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of $$k$$ k bases $$B_{1}, \dotsc , B_{k}$$ B 1 , ⋯ , B k of $$M$$ M such that the weight of the symmetric difference of any pair of these bases is at least $$d$$ d . The input to the Weighted Diverse Common Independent Sets problem consists of two matroids $$M_{1},M_{2}$$ M 1 , M 2 defined on the same ground set $$E$$ E , a weight function $$\omega :E\rightarrow \mathbb {N} $$ ω : E → N , and integers $$k\ge 1, d\ge 1$$ k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of $$k$$ k common independent sets $$I_{1}, \dotsc , I_{k}$$ I 1 , ⋯ , I k of $$M_{1}$$ M 1 and $$M_{2}$$ M 2 such that the weight of the symmetric difference of any pair of these sets is at least $$d$$ d . The input to the Diverse Perfect Matchings problem consists of a graph $$G$$ G and integers $$k\ge 1, d\ge 1$$ k ≥ 1 , d ≥ 1 . The task is to decide if $$G$$ G contains $$k$$ k perfect matchings $$M_{1},\dotsc ,M_{k}$$ M 1 , ⋯ , M k such that the symmetric difference of any two of these matchings is at least $$d$$ d . We show that none of these problems can be solved in polynomial time unless $${{\,\mathrm{\textsf{P}}\,}} ={{\,\mathrm{\textsf{NP}}\,}} $$ P = NP . We derive fixed-parameter tractable ( $${{\,\mathrm{\textsf{FPT}}\,}}$$ FPT ) algorithms for all three problems with $$(k,d)$$ ( k , d ) as the parameter, and present a $$poly(k,d)$$ p o l y ( k , d ) -sized kernel for Weighted Diverse Bases.

29 November 2021 in Algorithmica
Verified
Journal Article
Open access
PDF file
LJLars Jaffke
Lars Jaffke
PLPaloma T. Lima
Paloma T. Lima
GPGeevarghese Philip
Geevarghese Philip
A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with q colors. For fixed $$q \ge 2$$ q ≥ 2 , we give an $$\mathscr {O}^{\star }(q^{{\mathsf {tw}}})$$ O ⋆ ( q tw ) -time algorithm when the input graph is given together with one of its tree decompositions of width $${\mathsf {tw}} $$ tw . We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is $$\mathsf {XP}$$ XP parameterized by clique-width.