Bibtex entries for my publications
@inproceedings{PhilipRamanSikdar2009,
author = {Philip, Geevarghese and Raman, Venkatesh and Sikdar, Somnath },
title = {Solving {D}ominating {S}et in {L}arger {C}lasses of {G}raphs: {FPT} {A}lgorithms and {P}olynomial {K}ernels},
booktitle = {Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings},
editor = {Amos Fiat and Peter Sanders},
series = {Lecture Notes in Computer Science},
volume = {5757},
year = {2009},
pages = {694-705},
url = { publications/ds_kernel.pdf},
abstract = {We show that the k-Dominating Set problem is
fixed-parameter tractable (FPT) and has a polynomial kernel for
any class of graphs that exclude $K_{i,j}$ as a subgraph, for any
fixed i, j ≥ 1. This strictly includes every class of graphs for
which this problem has been previously shown to have FPT
algorithms and/or polynomial kernels. In particular, our result
implies that the problem restricted to bounded-degenerate graphs
has a polynomial kernel, solving an open problem posed by Alon and
Gutner. } }
@inproceedings{MisraPhilipRamanSaurabh2010,
author = {{M}isra, {N}eeldhara and {P}hilip, {G}eevarghese and {R}aman, {V}enkatesh
and {S}aurabh, {S}aket},
title = {{T}he effect of girth on the kernelization complexity of {C}onnected
{D}ominating {S}et},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010,
Chennai, India},
year = {2010},
editor = {Kamal Lodaya and Meena Mahajan},
volume = {8},
series = {LIPIcs},
pages = {96-107},
url = { publications/girthcds.pdf},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
abstract = {In the CONNECTED DOMINATING SET problem we are given
as input a graph G and a positive integer k, and are asked if
there is a set S of at most k vertices of G such that S is a
dominating set of G and the subgraph induced by S is
connected. This is a basic connectivity problem that is known to
be NP-complete, and it has been extensively studied using
several algorithmic approaches. In this paper we study the
effect of excluding short cycles, as a subgraph, on the
kernelization complexity of CONNECTED DOMINATING
SET. Kernelization algorithms are polynomial-time algorithms
that take an input and a positive integer k (the parameter) and
output an equivalent instance where the size of the new instance
and the new parameter are both bounded by some function
g(k). The new instance is called a g(k) kernel for the
problem. If g(k) is a polynomial then we say that the problem
admits polynomial kernels. The girth of a graph G is the length
of a shortest cycle in G. It turns out that CONNECTED DOMINATING
SET is ”hard” on graphs with small cycles, and becomes
progressively easier as the girth increases. More specifically,
we obtain the following interesting trichotomy: CONNECTED
DOMINATING SET
• does not have a kernel of any size on graphs of girth 3 or
4 (since the problem is W[2]-hard);
• admits a g(k) kernel, where g(k) is roughly $k^{O(k)}$ ,
on graphs of girth 5 or 6 but has no polynomial kernel
(unless the Polynomial Hierarchy (PH) collapses to the
third level) on these graphs;
• has a cubic $(O(k^3))$ kernel on graphs of girth at least
7. While there is a large and growing collection of
parameterized complexity results available for problems
on graph classes characterized by excluded minors, our
results add to the very few known in the field for graph
classes characterized by excluded subgraphs. } }
@inproceedings{PhilipRamanVillanger2010,
author = {{P}hilip, {G}eevarghese and {R}aman, {V}enkatesh and {V}illanger,
{Y}ngve},
title = {{A} {Q}uartic {K}ernel for {P}athwidth-{O}ne {V}ertex {D}eletion},
booktitle = {Graph Theoretic Concepts in Computer Science - 36th International
Workshop, WG 2010, Zar{\'o}s, Crete, Greece, June 28-30, 2010 Revised
Papers},
year = {2010},
volume = {6410},
series = {Lecture Notes in Computer Science},
pages = {196-207},
url = { publications/pwone.pdf},
abstract = {The pathwidth of a graph is a measure of how
path-like the graph is. Given a graph G and an integer k, the
problem of finding whether there exist at most k vertices in G
whose deletion results in a graph of pathwidth at most one is NP-
complete. We initiate the study of the parameterized complexity of
this problem, parameterized by k. We show that the problem has a
quartic vertex-kernel: We show that, given an input instance (G =
(V, E), k) where |V| = n, we can construct, in polynomial time, an
instance (G', k') such that (i) (G, k) is a YES instance if and
only if (G', k') is a YES instance, (ii) G has O(k^4) vertices,
and (iii) k' ≤ k. We also give a fixed parameter tractable (FPT)
algorithm for the problem that runs in O*(7^k · n^3) time. These
figures compare favorably with the best results known for the
closely related, and extensively studied, Feedback Vertex Set
problem.} }
@inproceedings{AmbalathBalasundaramHKoppulaMisraPhilipRamanujan2010,
author = {Ambalath, Abhimanyu M. and Balasundaram, Radheshyam and H., Chintan Rao and Koppula, Venkata and Misra, Neeldhara and Philip, Geevarghese and Ramanujan, M. S.},
title = {On the Kernelization Complexity of Colorful Motifs},
booktitle = {Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings},
year = {2010},
pages = {14-25},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {6478},
editor = {Venkatesh Raman and Saket Saurabh},
url = { publications/cm.pdf},
abstract = {The Colorful Motif problem asks if, given a
vertex-colored graph G, there exists a subset S of vertices of G
such that the graph induced by G on S is connected and contains
every color in the graph exactly once. The problem is motivated
by applications in computational biology and is also
well-studied from the theoretical point of view. In particular,
it is known to be NP-complete even on trees of maximum degree
three [Fellows et al, ICALP 2007]. In their pioneering paper
that introduced the color-coding technique, Alon et al. [STOC
1995] show, inter alia, that the problem is FPT on general
graphs. More recently, Cygan et al. [WG 2010] showed that
Colorful Motif is NP-complete on comb graphs, a special subclass
of the set of trees of maximum degree three. They also showed
that the problem is not likely to admit polynomial kernels on
forests.
We continue the study of the kernelization complexity of
the Colorful Motif problem restricted to simple graph
classes. Surprisingly, the infeasibility of polynomial
kernelization persists even when the input is restricted to comb
graphs. We demonstrate this by showing a simple but novel
composition algorithm. Further, we show that the problem
restricted to comb graphs admits polynomially many polynomial
kernels. To our knowledge, there are very few examples of problems
with many polynomial kernels known in the literature. We also show
hardness of polynomial kernelization for certain variants of the
problem on trees; this rules out a general class of approaches for
showing many polynomial kernels for the problem restricted to
trees. Finally, we show that the problem is unlikely to admit
polynomial kernels on another simple graph class, namely the set
of all graphs of diameter two. As an application of our results,
we settle the classical complexity of Connected Dominating Set on
graphs of diameter two — specifically, we show that it is
NP-complete.} }
@inproceedings{FernauFominPhilipSaurabh2010,
author = {{F}ernau, {H}enning and {F}omin, {F}edor {V}. and {P}hilip, {G}eevarghese
and {S}aurabh, {S}aket},
title = {{T}he {C}urse of {C}onnectivity: t-{T}otal {V}ertex({E}dge) {C}over},
booktitle = {Proceedings of the 16th Annual International Computing and Combinatorics Conference (COCOON 2010)},
year = {2010},
editor = {Thai, My T. and Sahni, Sartaj},
volume = {6196},
series = {LNCS},
pages = {34-43},
publisher = {Springer},
url = { publications/tvc.pdf},
abstract = {We investigate the effect of certain natural
connectivity constraints on the parameterized complexity of two
fundamental graph covering problems, namely k-VERTEX COVER and
k-EDGE COVER. Specifically, we impose the additional requirement
that each connected component of a solution have at least t
vertices (resp. edges from the solution), and call the problem
t-TOTAL VERTEX COVER (resp. t- TOTAL EDGE COVER ). We show that
– both problems remain fixed-parameter tractable with these
restrictions, with running times of the form $O^{∗}(c^{k})$ for
some constant c > 0 in each case;
– for every t ≥ 2, t-TOTAL VERTEX COVER has no polynomial kernel
unless the Polynomial Hierarchy collapses to the third level;
– for every t ≥ 2, t-TOTAL EDGE COVER has a linear vertex kernel
of size (t+1)k/t. These results significantly improve earlier
work on these problems.
Our no-poly-kernel result for t-TOTAL VERTEX COVER, and the known
NP-hardness result for t-TOTAL EDGE COVER , are in stark
contrast to the fact that k-VERTEX COVER has a 2k vertex kernel,
and that k-EDGE COVER is solvable in polynomial time. This
illustrates how even the slightest connectivity requirement
results in a drastic change in the tractability of problems —
the curse of connectivity!},
}
@inproceedings{MisraPhilipRamanSaurabhSikdar2010,
author = {Misra, Neeldhara and Philip, Geevarghese and Raman, Venkatesh and Saurabh, Saket and Sikdar, Somnath },
title = {{FPT} {A}lgorithms for {C}onnected {F}eedback {V}ertex {S}et},
booktitle = {WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010. Proceedings},
editor = {Md. Saidur Rahman, Satoshi Fujita},
series = {Lecture Notes in Computer Science},
volume = {5942},
year = {2010},
pages = {269-280},
url = { publications/cfvs.pdf},
abstract = {We study the recently introduced Connected Feedback
Vertex Set (CFVS) problem from the view-point of parameterized
algorithms. CFVS is the connected variant of the classical
Feedback Vertex Set problem and is defined as follows: given a
graph G = (V, E) and an integer k, decide whether there exists F ⊆
V , |F | ≤ k, such that G[V \ F] is a forest and G[F] is
connected. We show that Connected Feedback Vertex Set can be
solved in time $O(2^{O(k)} n^{O(1)})$ on general graphs and in
time $O(2^{O(\sqrt{k} log k)} n^{O(1)})$ on graphs excluding a
fixed graph H as a minor. Our result on general undirected graphs
uses, as a subroutine, a parameterized algorithm for Group Steiner
Tree, a well studied variant of Steiner Tree. We find the
algorithm for Group Steiner Tree of independent interest and
believe that it could be useful for obtaining parameterized
algorithms for other connectivity problems. } }
@InProceedings{FernauFominLokshtanovMnichPhilipSaurabh2011,
author = {Fernau, Henning and Fomin, Fedor V. and Lokshtanov, Daniel and Mnich, Matthias and Philip, Geevarghese and Saurabh, Saket},
title = {Ranking and Drawing in Subexponential Time},
booktitle = {Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers},
editor = {Iliopoulos, Costas S. and Smyth, William F.},
series = {Lecture Notes in Computer Science},
volume = {6460},
year = {2010},
pages = {337-348},
url = { publications/oscm-kemeny.pdf},
abstract = {In this paper we obtain parameterized
subexponential-time algorithms for p-Kemeny Aggregation (p-KAGG)
— a problem in social choice theory — and for p-One-Sided
Crossing Minimization (p-OSCM) – a problem in graph
drawing. These algorithms run in time $O^{*}(2^{O(\sqrt{k}\log
k)})$, where $k$ is the parameter, and significantly improve the
previous best algorithms with running times $O^{∗}(1.403^{k})$
and $O^{∗}(1.4656^{k})$, respectively. We also study natural
“above-guarantee” versions of these problems and show them to be
fixed parameter tractable. In fact, we show that the
above-guarantee versions are equivalent to a weighted variant of
p-Directed Feedback Arc Set. Our results for the above-guarantee
version of p-KAGG reveal an interesting contrast. We show that
when the number of “votes” in the input to p-KAGG is odd the
above guarantee version can still be solved in time
$O^{*}(2^{O(\sqrt{k}\log k)})$, while if it is even then the
problem cannot have a subexponential time algorithm unless the
exponential time hypothesis fails (equivalently, unless
FPT=M[1]). },
}
@InProceedings{FominLokshtanovMisraPhilipSaurabh2011,
author = {{F}omin, {F}edor {V}. and {L}okshtanov, {D}aniel and {M}isra, {N}eeldhara
and {P}hilip, {G}eevarghese and {S}aurabh, {S}aket},
title = {{H}itting {F}orbidden {M}inors: {A}pproximation and {K}ernelization},
booktitle = {28th International Symposium on Theoretical Aspects of Computer
Science, STACS 2011, March 10-12, 2011, Dortmund, Germany},
editor = {Schwentick, Thomas and D{\"u}rr, Christoph},
series = {LIPIcs},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
volume = {9},
year = {2011},
pages = {189-200},
url = { publications/theta.pdf},
abstract = {We study a general class of problems called
p-F-Deletion problems. In an p-F-Deletion problem, we are
asked whether a subset of at most k vertices can be
deleted from a graph G such that the resulting graph does
not contain as a minor any graph from the family F of
forbidden minors. We obtain a number of algorithmic
results on the p-F-Deletion problem when F contains a
planar graph. We give
- a linear vertex kernel on graphs excluding t-claw K1,t
, the star with t leves, as an induced subgraph, where t
is a fixed integer.
- an approximation algorithm achieving an approximation
ratio of O(log^{3/2} OPT ), where OPT is the size of an
optimal solution on general undirected graphs.
Finally, we obtain polynomial kernels for the case when F
only contains graph \(\Theta_{c}\) as a minor for a fixed
integer c. The graph \(\Theta_{c}\) consists of two
vertices connected by c parallel edges. Even though this
may appear to be a very restricted class of problems it
already encompasses well-studied problems such as Vertex
Cover, Feedback Vertex Set and Diamond Hitting Set. The
generic kernelization algorithm is based on a non-trivial
application of protrusion techniques, previously used only
for problems on topological graph classes.} }