Institute Logo

Publications

A list of some of my papers and manuscripts.

Papers

Bidimensionality and Geometric Graphs
(with F. V. Fomin and D. Lokshtanov).                                          
To appear in SODA 2012.
Linear Kernels for (Connected) Dominating Set on H-minor-free graphs
(with F. V. Fomin, D. Lokshtanov and D. M. Thilikos).                                          
To appear in SODA 2012.
Faster Algorithms for Finding and Counting Subgraphs
(with F. V. Fomin, D. Lokshtanov, V. Raman and B. V. R. Rao).                                          
To appear in Journal of Computer System Sciences.
Paths, Flowers and Vertex Cover
(with V. Raman and M. S. Ramanujan).                                          
In the proceedings of ESA '11 (Springer Verlag, LNCS 6942), 382-393.
Hitting and Harvesting Pumpkins
(with G. Joret, C. Paul, I. Sau and S. Thomassť).                                          
In the proceedings of ESA '11 (Springer Verlag, LNCS 6942), 1394-407.
On Cutwidth Parameterized by Vertex Cover
(with M. Cygan, D. Lokshtanov, M. Pilipczuk and M. Pilipczuk ).                                          
In the proceedings of IPEC '11.
On The Hardness of Losing Width
(with M. Cygan, D. Lokshtanov, M. Pilipczuk and M. Pilipczuk ).                                          
In the proceedings of IPEC '11.
Algorithmic Aspects of Dominator Colorings in Graphs
(with S. Arumugam, K. R. Chandrasekar, N. Misra and G. Philip).                                          
In the proceedings of IWOCA '11.
Planar k-Path in Subexponential Time and Polynomial Space
(with D. Lokshtanov and M. Mnich).                                          
In the proceedings of WG '11.
Tight Bounds for Linkages in Planar Graphs
(with I. Adler, S. G. Kolliopoulos, P. K. Krause, D. Lokshtanov and D. M. Thilikos).                                          
In the proceedings of ICALP (1) '11 (Springer Verlag, LNCS 6755), 110-121.
Parameterized Independent Feedback Vertex Set
(with N. Misra, G. Philip and V. Raman).                                          
In the proceedings of COCOON '11 (Springer Verlag, LNCS 6842), 98-109.
Hitting Forbidden Minors: Approximation and Kernelization
(with F. V. Fomin, D. Lokshtanov, N. Misra and G. Philip).                                          
In the proceedings of STACS '11 (LIPIcs, Volume 9), 189-200.
Approximation Algorithms for Minimum Chain Vertex Deletion
(with S. Mishra, M. Kumar and N. Safina Devi).                                         
In the proceedings of WALCOM '11 (Springer Verlag, LNCS 6552), 21-32.
Slightly Superexponential Parameterized Problems
(with D. Lokshtanov and D. Marx).                                          
In the proceedings of SODA '11, 760-776.
Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal
(with D. Lokshtanov and D. Marx).                                          
In the proceedings of SODA '11, 777-789.
Bidimensionality and EPTAS
(with F. Fomin, D. Lokshtanov and V. Raman).                                          
In the proceedings of SODA '11, 748-759.
The effect of girth on the kernelization complexity of Connected Dominating Set
(with N. Misra, G. Philip and V. Raman).                                          
To appear in the proceedings of FSTTCS '10 (LIPIcs, Volume 8), 96-107.
Determining the Winner of a Dodgson Election is Hard
(with M. Fellows, B. Jansen, D. Lokshtanov and F. A. Rosamond).                                          
In the proceedings of FSTTCS '10 (LIPIcs, Volume 8), 459-468.
Parameterized Algorithms for Boxicity
(with A. Adiga and R. Chitnis).                                          
In the proceedings of ISAAC '10 (Springer Verlag, LNCS 6506), 366-377.
Ranking and Drawing in Subexponential Time
(with H.Fernau, F.V.Fomin, D.Lokshtanov, M. Mnich and G.Philip ).                                          
In the proceedings of IWOCA '10 (Springer Verlag, LNCS 6460), 337-348.
Fast Local Search Algorithm for Weighted Feedback Arc Set in Tournaments
(with F. Fomin, D. Lokshtanov and V. Raman).                                          
In the proceedings of AAAI '10.
Imbalance Is Fixed Parameter Tractable
(with D. Lokshtanov and N. Misra).                                          
In the proceedings of COCOON '10 (Springer Verlag, LNCS 6196), 199-208.
The Curse of Connectivity: t-Total Vertex (Edge) Cover
(with H. Fernau, F. V. Fomin and G. Philip).                                          
In the proceedings of COCOON '10 (Springer Verlag, LNCS 6196), 34-43.
Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing
(with P. Heggernes, D. Kratsch, D. Lokshtanov and V. Raman).                                          
In the proceedings of SWAT '10 (Springer Verlag, LNCS 6139), 334-345.
Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs
(with F. Dorn, F. Fomin, D. Lokshtanov and V. Raman).                                          
In the proceedings of STACS '10, 251-262.
Sharp Separation and Applications to Exact and Parameterized Algorithms
(with F. Fomin, D. Lokshtanov and F. Grandoni).                                          
In the proceedings of LATIN '10 (Springer Verlag, LNCS 6034), 72-83.
FPT Algorithms for Connected Feedback Vertex Set
(with N. Misra, G. Philip, V. Raman and S. Sikdar).                                          
In the proceedings of WALCOM '10 (Springer Verlag, LNCS 5942), 269-280.
Algorithmic Lower Bounds for Problems Parameterized by Clique-width
(with F. Fomin, P. Golovach and D. Lokshtanov).                                          
In the proceedings of SODA '10, 493-502.
Bidimensionality and Kernels
(with F. Fomin, D. Lokshtanov and D. M. Thilikos).                                          
In the proceedings of SODA '10, 503-510.
Subexponential Algorithms for Partial Cover Problems
(with F. Fomin, D. Lokshtanov and V. Raman).                                          
In the proceedings of FSTTCS '09, 193-201.
Kernels for Feedback Arc Set In Tournaments
(with S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez and S. Thomasse).                                          
In the proceedings of FSTTCS '09, 37-47.
Bandwidth on AT-free graphs
(with P. Golovach, P. Heggernes, D. Kratsch, D. Lokshtanov and D. Meister).                                          
In the proceedings of ISAAC '09 (Springer Verlag, LNCS 5878), 573-582.
A Linear Vertex Kernel for Maximum Internal Spanning Tree
(with F. V. Fomin, S. Gaspers and S. Thomasse).
In the proceedings of ISAAC '09 (Springer Verlag, LNCS 5878), 275-282.
(Meta) Kernelization
(with H.L.Bodlaender, F.V.Fomin, D.Lokshtanov, E.Penninkx and D.M.Thilikos).                                          
In the proceedings of FOCS '09, 629-638.
Even Faster Algorithm for Set Splitting!
(with D. Lokshtanov).                                          
In the proceedings of IWPEC '09 (Springer Verlag, LNCS 5917), 288-299.
On the Directed Degree-Preserving Spanning Tree Problem
(with D. Lokshtanov, V. Raman and S. Sikdar).                                          
In the proceedings of IWPEC '09 (Springer Verlag, LNCS 5917), 276-287.
Simpler Parameterized Algorithm for OCT
(with D. Lokshtanov and S. Sikdar).                                          
In the proceedings of IWOCA '09 (Springer Verlag, LNCS 5874), 380-384.
An Exact Algorithm for Minimum Distortion Embedding
(with F. V. Fomin and D. Lokshtanov).                                          
In the proceedings of WG '09 (Springer Verlag, LNCS 5911), 112-121.
The Budgeted Unique Coverage Problem and Color Coding
(with N. Misra, V. Raman and S. Sikdar).                                          
In the proceedings of CSR '09 (Springer Verlag, LNCS 5675), 310-321.
Fast FAST
(with N. Alon and D. Lokshtanov).                                          
In the proceedings of ICALP '09 (Springer Verlag, ARCoSS, LNCS 5555), 49-58.
Counting Subgraphs via Homomorphisms
(with O. Amini and F. V. Fomin).                                          
In the proceedings of ICALP '09(Springer Verlag, ARCoSS, LNCS 5555), 71-82.
Incompressibility through Colors and IDs
(with M. Dom and D. Lokshtanov).                                          
In the proceedings of ICALP '09(Springer Verlag, ARCoSS, LNCS 5555), 378-389.
Distortion is Fixed Parameter Tractable
(with M. Fellows, F. V. Fomin D. Lokshtanov, E.Losievskaja and F. A. Rosamond).                                          
In the proceedings of ICALP '09(Springer Verlag, ARCoSS, LNCS 5555), 463-474.
Local Search: Is brute-force avoidable?
(with M. Fellows, F. V. Fomin, D. Lokshtanov, F. A. Rosamond and Y. Villanger).                                          
In the proceedings of IJCAI '09, 486-491.
Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
(with N. Cohen, F. V. Fomin, G. Gutin, E. J. Kim and A. Yeo).                                          
In the proceedings of COCOON '09(Springer Verlag, LNCS 5609), 37-46.
Linear Kernel for Planar Connected Dominating Set
(with D. Lokshtanov and M. Mnich).                                          
In the proceedings of TAMC '09(Springer Verlag, LNCS 5532), 281-290.
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
(with H. Fernau, F. V. Fomin, D. Lokshtanov, D. Raible and Y. Villanger).                                        
In the proceedings of STACS '09, 421-432.
Clique-width: On the Price of Generality
(with F. V. Fomin, D. Lokshtanov and P. A. Golovach).                                          
In the proceedings of SODA '09, 825-834.
Spanning Directed Tree with many Leaves
(with N. Alon, F. V. Fomin, G. Gutin and M. Krivelevich).
Siam Journal on Discrete Mathematics. Volume 23, Issue 1, Pages 466-476.
Preliminary version of the paper appeared in the proceedings of FSTTCS 2007.
The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
(with M. Fellows, D. Lokshtanov, N. Misra, M. Mnich and F. A. Rosamond).
Accepted to appear in `Theory of Computing Systems', Springer Verlag.
Konig Deletion Sets and Vertex Covers Above the Matching Size
(with S. Mishra, V. Raman, and S. Sikdar).
In the proceedings of ISAAC '08(Springer Verlag, LNCS 5369), 836-847.
Graph Layout problems Parameterized by Vertex Cover
(with M. Fellows, D. Lokshtanov, N. Misra and F. A. Rosamond).
In the proceedings of ISAAC '08(Springer Verlag, LNCS 5369), 294-305.
Implicit Branching and Parameterized Partial Cover Problems
(with O. Amini and F. Fomin).
In the proceedings of FSTTCS '08.
Degree-Constrained Subgraph Problems : Hardness and Approximation Results
(with O. Amini, D. Peleg, S. Pérennes, and I. Sau).
In the proceedings of WAOA '08(Springer Verlag, LNCS 5426), 29-42.
Parametrized Complexity of the Smallest Degree Constrained Subgraph Problem
(with O. Amini and I. Sau).
In the proceedings of IWPEC'08 (Springer Verlag, LNCS 5018), 13-29.
Capacitated Domination and Covering: A Parameterized Perspective
(with M. Dom, D. Lokshtanov and Y. Villanger).
In the proceedings of IWPEC'08: (Springer Verlag, LNCS 5018) 78-90.
A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
(with S. Gaspers, and A. A. Stepanov).
In the proceedings of TAMC'08: (Springer Verlag, LNCS 4978) 479-489.
Parameterized Algorithms for Generalized Domination
(with V. Raman, and S. Srihari).
In the proceedings of COCOA 2008: (Springer Verlag, LNCS 5165) 116-126.
Iterative Compression and Exact Algorithms
(with F. V. Fomin, S. Gaspers, D. Kratsch, and M. Liedloff).
In the proceedings of MFCS 2008: (Springer Verlag, LNCS 5162) 335-346.
Improving the gap of Erdos-Posa property for minor-closed graph classes
(with F. V. Fomin and D. M. Thilikos).
In the proceedings of 7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2008.
On Two Techniques of Combining Branching and Treewidth
(with F. V. Fomin, S. Gaspers, and A. A. Stepanov).
Algorithmica. Volume 54, Issue 2, Pages 181-207 (2009).
A preliminary version of the paper appeared in the proceedings of ISAAC 2006.
Short Cycles make W-hard problems hard: FPT algorithms for W-hard problems in Graphs with
no short cycles (with V. Raman)
Algorithmica. Volume 52, Issue 2, Pages 203-225 (2008).
A preliminary version of the paper appeared in the proceedings of SWAT 2006.
The Complexity of Finding Subgraphs whose Matching Number Equals the Vertex Cover Number
(with S. Mishra, V. Raman, S. Sikdar, C. R. Subramanian).
In the proceedings of ISSAC '07: (Springer Verlag, LNCS 4835) 268-279.
On the Complexity of Some Colorful Problems Parameterized by Treewidth
(with M. Fellows, F. V. Fomin, D. Lokshtanov, F. Rosamond, S. Szeider and C. Thomassen).
In the proceedings of COCOA'07: (Springer Verlag, LNCS 4616) 366-377. (Invited Paper.)
Parameterized Algorithms for Directed Maximum Leaf Problems
(with N. Alon, F. V. Fomin, G. Gutin and M. Krivelevich).
In the proceedings of ICALP'07: (Springer Verlag, LNCS 4596) 352-362.
Improved Exact Algorithms for Counting 3- and 4- Colorings
(with F. V. Fomin and S. Gaspers)
In the proceedings of COCOON'07: (Springer Verlag, LNCS 4598) 65-74.
Improved Fixed Parameter Tractable Algorithms for Two Edge Problems -- MAXCUT and MAXDAG
(with V. Raman).
Information Processing Letters (IPL). Volume 104(2), Pages 65-72 (2007)
Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques
(with V. Raman and S. Sikdar).
Theory of Computing Systems. Volume 41, Issue 3, Pages 563-587 (2007).
A preliminary version of the paper appeared in the proceedings of ICTCS 2005.
Exact and Parameterized Algorithms through (old and new) Structural Graph theoretical Results
(with V. Raman).
In the proceedings of the International Conference on Discrete Mathematics (2006), 177-189.
Fast Exponential Algorithms for Maximum $r$-Regular Induced Subgraph Problems
(with S. Gupta and V. Raman).
In the proceedings of FSTTSC '06: (Springer Verlag, LNCS 4337) 139-151.
Faster Fixed Parameter Tractable Algorithms for Finding Feedback Vertex Sets
(with V. Raman and C. R. Subramanian).
ACM Transactions on Algorithms (TALG). Volume 2, Issue 3, Pages 403-415 (2006).
Preliminary versions of the paper appeared in the proceedings of ISAAC 2002 and GRACO 2005.
Parameterized Algorithms for Feedback Set Problems and Their Duals in Tournaments
(with V. Raman).
Theoretical Computer Science (TCS). Volume 351, Issue 3, Pages 446-458 (2006).
Preliminary versions of the paper appeared in the proceedings of WADS 2003 and IWPEC 2004.



Surveys and Book Chapters