Institute Logo

Publications

A list of some of my papers and manuscripts.

Papers

Algorithmic Lower Bounds for Problems Parameterized by Clique-width
(with F. Fomin, P. Golovach and D. Lokshtanov).                                          
To appear in the proceedings of SODA '10.
Bidimensionality and Kernels
(with F. Fomin, D. Lokshtanov and D. M. Thilikos).                                          
To appear in the proceedings of SODA '10.
Subexponential Algorithms for Partial Cover Problems
(with F. Fomin, D. Lokshtanov and V. Raman).                                          
To appear in the proceedings of FSTTCS '09.
Kernels for Feedback Arc Set In Tournaments
(with S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez and S. Thomasse).                                          
To appear in the proceedings of FSTTCS '09.
Bandwidth on AT-free graphs
(with P. Golovach, P. Heggernes, D. Kratsch, D. Lokshtanov and D. Meister).                                          
To appear in the proceedings of ISAAC '09.
A Linear Vertex Kernel for Maximum Internal Spanning Tree
(with F. V. Fomin, S. Gaspers and S. Thomasse).
To appear in the proceedings of ISAAC '09.
(Meta) Kernelization
(with H.L.Bodlaender, F.V.Fomin, D.Lokshtanov, E.Penninkx and D.M.Thilikos).                                          
To appear in the proceedings of FOCS '09.
Even Faster Algorithm for Set Splitting!
(with D. Lokshtanov).                                          
To appear in the proceedings of IWPEC '09.
On the Directed Degree-Preserving Spanning Tree Problem
(with D. Lokshtanov, V. Raman and S. Sikdar).                                          
To appear in the proceedings of IWPEC '09.
Simpler Parameterized Algorithm for OCT
(with D. Lokshtanov and S. Sikdar).                                          
To appear in the proceedings of IWOCA '09.
An Exact Algorithm for Minimum Distortion Embedding
(with F. V. Fomin and D. Lokshtanov).                                          
To appear in the proceedings of WG '09.
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.



Manuscripts