-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathresearch.html
More file actions
1713 lines (1663 loc) · 58.5 KB
/
research.html
File metadata and controls
1713 lines (1663 loc) · 58.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<title>Prafullkumar Tale</title>
<meta name="description" content="Prafullkumar's homepage" />
<meta name="author" content="Prafullkumar Tale" />
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="stylesheet" type="text/css" href="common.css" media="all">
<link rel="icon" href="images/favicon.ico" type="image/x-icon" sizes="20x20">
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.4.1/css/bootstrap.min.css">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.5.1/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.4.1/js/bootstrap.min.js"></script>
<link href='https://fonts.googleapis.com/css?family=ABeeZee' rel='stylesheet' type='text/css' />
<link href='https://fonts.googleapis.com/css?family=Enriqueta' rel='stylesheet' type='text/css' />
</head>
<body>
<div class="container">
<!-- Header section starts -->
<div class="header-section">
<div>
<div>
<h1><a href="index.html">Prafullkumar Tale</a></h1>
</div>
</div>
<nav class="navbar navbar-default">
<div class="container-fluid">
<ul class="nav navbar-nav">
<li><a href="index.html">Home</a></li>
<li class="active"><a href="research.html">Research</a></li>
<li><a href="experience.html">Experience</a></li>
<li><a href="teaching.html">Teaching</a></li>
<li><a href="contact.html">Contact</a></li>
<li><a href="misc.html">Misc</a></li>
</ul>
</div>
</nav>
</div>
<!-- Header section ends -->
<!-- Main content starts -->
<p> See <a href="https://dblp.org/pid/186/2898.html" , target="_blank">DBLP</a> |
<a href="https://arxiv.org/search/cs?searchtype=author&query=Tale,+P" , target="_blank">arXiv</a> |
<a href="https://scholar.google.com/citations?user=Wk72W0kAAAAJ&hl=en" , target="_blank">Google Scholar</a>.
</p>
<p>
<i> In theoretical computer science,
the authors’ name appear in alphabetical order of their last names.
Also, a norm is to publish preliminary results
in a conference (which have page limits) and their
full version in a journal.
<!--p>Gray, yellow, and green colors indicate
unpublished articles, conference publication,
and journal publications, respectively.<p-->
</i>
</p>
<br/>
<!-- PASTE HERE -->
<!--div class="bibentry-article">
<div>
<table>
<tr><td class="paper">[ P-XX ] Paper-Title </td>
</tr>
<tr>
<td> with <i> co-authors </i></td>
</tr>
<tr>
<td class="conference">
[C-XX] Conference.
</td>
</tr>
<tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr>
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-pXX">Summary</a> |
<a href="arXiv-Link" target="_blank">Paper</a> |
<a href="./docs/XXXXXX" target="_blank">Presentation</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-pXX" class="collapse">
Summary of the paper
</p>
</div>
</div-->
<!-- PASTE HERE -->
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-38 ] Algorithms and Hardness for Geodetic Set
on Tree-like Digraphs </td>
</tr>
<tr>
<td> with <i> Florent Foucaud, Narges Ghareghani, Lucas Lorieau,
Morteza Mohammad-Noori, and
Rasa Parvini Oskuei </i></td>
</tr>
<tr>
<td class="conference">
[C-32] The International Conference on Algorithms and Discrete Applied Mathematics
<b>CALDAM</b> 2026.
</td>
</tr>
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p38">Summary</a> |
<a href="arXiv-Link" target="_blank">Paper</a> |
<a href="./docs/2026-CALDAM.pdf" target="_blank">Presentation by L. Lorieau</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p38" class="collapse">
In the Geodetic Set problem, an input is a digraph G and
integer k, and the objective is to decide whether there exists a vertex
subset S of size k such that any vertex in V (G) \ S lies on a
shortest path between two vertices in S.
We focus on directed graphs (with or without 2-cyles) whose underlying
undirected graph is close to a tree.
</p>
</div>
</div>
<br/>
<!-- PASTE HERE -->
<div class="bibentry-article">
<div>
<table>
<tr><td class="paper">[ P-37 ] Parameterized Complexity of Shortest Path Partition: Treewidth and Diameter </td>
</tr>
<tr>
<td> with <i> Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari </i></td>
</tr>
<!--tr>
<td class="conference">
[C-XX] Conference.
</td>
</tr-->
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p37">Summary</a> |
<a href="https://arxiv.org/abs/2508.05448" target="_blank"> Paper</a> |
<!--a href="./docs/XXXXXX" target="_blank">Presentation</a-->
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p37" class="collapse">
In the Isometric Path Partition problem, the input is a graph G with n vertices and
an integer k, and the objective is to determine whether the vertices of G can be partitioned
into k vertex-disjoint shortest paths.
We investigate the parameterized complexity of the problem
when parameterized by treewidth and treewidth plus diameter.
</p>
</div>
</div>
<br/>
<!-- PASTE HERE -->
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-36 ] The Parameterized Complexity of Computing the VC-Dimension </td>
</tr>
<tr>
<td> with <i> Florent Foucaud, Harmender Gahlawat, Fionn Mc Inerney </i></td>
</tr>
<tr>
<td class="conference">
[C-31] Annual Conference on Neural Information Processing Systems, <b> NeurIPS </b> 2025.
</td>
</tr>
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p36">Summary</a> |
<a href="https://arxiv.org/abs/2510.17451" target="_blank">Paper</a> |
<a href="./docs/2025-NeurIPS.pdf" target="_blank">Poster by F. Mc Inerney </a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p36" class="collapse">
The VC-dimension is a fundamental and well-studied measure of the complexity
of a set system (or hypergraph) that is central to many areas of machine learning.
We establish several new results on the complexity of computing the VC-dimension.
</p>
</div>
</div>
<br/>
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-35 ] A Finer View of the Parameterized Landscape of Labeled Graph Contractions </td>
</tr>
<tr>
<td> with <i> Yashaswini Mathur </i></td>
</tr>
<tr>
<td class="conference">
[C-30] Foundations of Software Technology and Theoretical Computer Science, <b>FSTTCS</b> 2025
</td>
</tr>
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p35">Summary</a> |
<a href="https://arxiv.org/abs/2510.06102" target="_blank">Paper</a> |
<a href="./docs/2025-FSTTCS.pdf" target="_blank">Presentation by Y. Mathur </a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p35" class="collapse">
We study the Labeled Contractibility problem,
where the input consists of two vertex-labeled graphs G and H,
and the goal is to determine whether H can
be obtained from G via a sequence of edge contractions.
Lafond and Marchand [WADS 2025] initiated the parameterized
complexity of the problem. We improve their results
and answer some open questions from their article.
</p>
</div>
</div>
<br/>
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-34 ] Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number </td>
</tr>
<tr>
<td><i> (This is a single author paper) </i></td>
</tr>
<tr>
<td class="conference">
[ C-29 ] International Symposium on Parameterized and Exact Computation, <b>IPEC</b> 2025.
</td>
</tr>
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p34">Summary</a> |
<a href="https://arxiv.org/abs/2504.17862" target="_blank">Paper</a> |
<a | href="./docs/2025-IPEC.pdf" target="_blank">Presentation</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p34" class="collapse">
In the Geodetic Set problem, the input consists of a graph G and a positive integer k. The goal is to determine whether there exists a subset S of vertices of size k such that every vertex in the graph is included in a shortest path between two vertices in S.
We prove that the problem remains NP-hard on graphs of constant pathwidth and feedback vertex set number answering the open question by
Kellerhals and Koana [IPEC 2020].
</p>
</div>
</div>
<br/>
<div class="bibentry-article">
<div>
<table>
<tr><td class="paper">[ P-33 ] Revisiting Token Sliding on Chordal Graphs </td>
</tr>
<tr>
<td> with <i> Rajat Adak, Saraswati Girish Nanoti </i></td>
</tr>
<!--tr>
<td class="conference">
[C-XX] Conference.
</td>
</tr-->
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p33">Summary</a> |
<a href="https://arxiv.org/abs/2502.12749" target="_blank">Paper</a>
<!--a href="./docs/XXXXXX" target="_blank"> | Presentation</a-->
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p33" class="collapse">
In the Token Sliding-Connectivity problem, the input is a graph
G and an integer k, and the objective is to determine whether the
reconfiguration graph TSk(G) of G is connected.
The vertices of TSk(G) are k-independent sets of G, and two vertices are
adjacent if and only if one can transform one of the two corresponding
independent sets into the other by sliding a vertex (also called a token) along
an edge.
We study the parameterized complexity of the problem for a parameter called
leafage and answer the questions by Bonamy and Bousquet [WG'17] along the way.
We prove similar results for a closely related problem called Token Sliding-Reachability. In this problem, the input is a graph G with two of its k-independent sets I and J, and the objective is to determine whether there is a sequence of valid token sliding moves that transform I into J.
</p>
</div>
</div>
<br/>
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-32 ] Robust Contraction Decomposition for Minor-Free Graphs and its Applications
</td>
</tr>
<tr>
<td> with <i> Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Dániel Marx, Pranabendu Misra, Daniel Neuen, Saket Saurabh, and Jie Xue </i> </td>
</tr>
<tr>
<td class="conference">
[C-28] International Colloquium on Automata, Languages and Programming, <b>ICALP</b> 2025.
</td>
<tr>
<tr><td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p32"> Summary</a> |
<a href="https://arxiv.org/abs/2412.04145" target="_blank">Paper</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p32" class="collapse">
We prove a robust contraction decomposition theorem
for H-minor-free graphs, which states that given an
H-minor-free graph G and an integer p,
one can partition in polynomial time the
vertices of G into p sets Z1,...,Zp such that
tw(G/(Zi∖ Z′)) = O(p + |Z′|) for all
i in [p] and Z′ subset of Zi.
This results in subexponential FPT or XP algorithm
for every vertex/edge deletion problems on H-minor-free
graphs that can be formulated as
Permutation CSP Deletion or
2-Conn Permutation CSP Deletion.
Consequently, we obtain the first subexponential-time
parameterized algorithms for Subset Feedback Vertex Set,
Subset Odd Cycle Transversal, Subset Group Feedback Vertex
Set,
2-Conn Component Order Connectivity on H-minor-free
graphs.
For other problems which already have subexponential-time
parameterized algorithms on H-minor-free graphs (e.g., Odd
Cycle Transversal, Vertex Multiway Cut, Vertex Multicut,
etc.), our theorem gives much simpler algorithms of the
same running time.
</p>
</div>
</div>
<br/>
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-31 ] Structural Parameterization of Locating-Dominating Set and Test Cover </td>
</tr>
<tr>
<td> with <i> Dipayan Chakraborty, Florent Foucaud,
and Diptapriyo Majumdar </i> </td>
</tr>
<tr>
<td class="conference">
[C-27] International Conference on Algorithms and Complexity <b>CIAC</b>, 2025.
</td>
<tr>
<tr><td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p31">Summary</a> |
<a href="https://arxiv.org/abs/2411.17948" target="_blank">Paper</a> |
<a href="./docs/2025-CIAC.pdf" target="_blank">Presentation by D. Chakraborty</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p31" class="collapse">
We investigate structural parameterizations the
two mentioned problem when parameters are vertex
cover and feedback edge set number.
The later parameterization resolves an open question
in the literature. We also prove that the problems
do not admit polynomial compressions when
the parameter is the number of vertices (under standard
assumption).
</p>
</div>
</div>
<br/>
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-30 ] Metric Dimension and Geodetic Set Parameterized by Vertex Cover</td>
</tr>
<tr>
<td> with <i> Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, and Roohani Sharma </i> </td>
</tr>
<tr>
<td class="conference">
[C-26] International Symposium on Theoretical Aspects of Computer Science, <b>STACS</b>, 2025.
</td>
<tr>
<tr><td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p30">Summary</a> |
<a href="https://arxiv.org/abs/2405.01344" target="_blank">Paper</a> |
<a href="./docs/2025-STACS.pdf" target="_blank">Presentation</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p30" class="collapse">
We observe that both problems admit an FPT algorithm
running in time 2^O(vc^2) poly(n),
and a kernelization algorithm that outputs a kernel with
2^O(vc) vertices.
We prove that both these results are optimal under
the Exponential Time Hypothesis (ETH).
We only know of one other problem in the literature that
admits such a tight algorithmic lower bound.
Also, the list of known problems with exponential lower
bounds on the number of vertices in kernelized instances
is very short.
</p>
</div>
</div>
<br/>
<div class="bibentry-journal">
<div>
<table>
<tr><td class="paper">[ P-29 ] Telephone Broadcast on Graphs of Treewidth Two</td>
</tr>
<tr>
<td> <i> This is a single author paper.
The first version is with title
`Double Exponential Lower Bound for Telephone Broadcast'.</i>
</tr>
<tr>
<td class="journal">
[J-21] Theoretical Computer Science, <b> TCS </b>, Volume 1045: 115282, 2025.
</td>
</tr>
<tr><td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p29">Summary</a> |
<a href="https://arxiv.org/abs/2403.03501" target="_blank">Paper (arXiv)</a>,
<a href="https://www.sciencedirect.com/science/article/pii/S0304397525002208" target="_blank">
Paper (TCS)</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p29" class="collapse">
In this article, we studied the Telephone Broadcast problem and answered two open question by
<a href="https://arxiv.org/abs/2306.01536" target="_blank">Fomin et al.</a>.
Our reductions results in somewhat rare results.
First, the problem admits a double exponential lower
bound when parameterized by the solution
size under the ETH.
Second, we prove that the problem is NP-complete even on
graphs of feedback vertex set number one, and hence on
graphs of tree-width at most two. Hence, this
result proves very tight polynomial/NP-completeness
dichotomy separating treewidth one from treewidth two,
which is a rare phenomenon.
</p>
</div>
</div>
<br/>
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-28 ] Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover </td>
</tr>
<tr>
<td> with <i> Dipayan Chakraborty, Florent Foucaud,
Diptapriyo Majumdar </i></td>
</tr>
<tr>
<td class="conference">
[C-25] International Symposium on Algorithms and Computation, <b>ISAAC</b> 2024.
</td>
<tr>
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p281">Summary</a> |
<a href="https://arxiv.org/abs/2402.08346" target="_blank">Paper</a> |
<a href="./docs/2024-ISAAC.pdf" target="_blank">Presentation</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p281" class="collapse">
In this article, we presented several results that
advances our understanding of the algorithmic
complexity of Locating-Dominating Set and Test Cover.
Moreover, we believe the techniques used in this article,
which are build on [P-27] can be applied to other
identification problems to obtain
relatively rare conditional lower bounds.
</p>
</div>
</div>
<br/>
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-27 ]
Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth and Vertex Cover </td>
</tr>
<tr>
<td> with <i> Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, and Roohani Sharma </i> </td>
</tr>
<tr>
<td class="conference">
[C-24] International Colloquium on Automata, Languages and Programming, <b>ICALP</b> 2024.
</td>
</tr>
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p27">Summary</a> |
<a href="https://arxiv.org/abs/2307.08149" target="_blank"> Paper </a> |
<a href="./docs/2024-ICALP-Presentation.pdf" target="_blank">Presentation by L. Khazaliya</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p27" class="collapse">
All the known conditional lower bounds of the form 2^{2^{o(tw)}}
are for the problems that are `complete' for the classes higher than NP in the polynomial
hierarchy.
Our results demonstrate, for the first time, that it is not necessary to go higher
up in the polynomial hierarchy to achieve double-exponential lower bounds:
we derive double-exponential lower bounds in the treewidth (tw) and the vertex
cover number (vc), for natural, important, and
well-studied metric-based NP-complete graph problems.
</p>
</div>
</div>
<br/>
<div class="bibentry-journal">
<div>
<table>
<tr><td class="paper">[ P-26 ] Revisiting Path Contraction and Cycle Contraction </td>
</tr>
<tr>
<td> with <i> R. Krithika, Kutty Malu V K </i></td>
</tr>
<tr>
<td class="conference">
[C-23] Workshop on Graph-Theoretic Concepts in Computer Science, <b>WG</b> 2024.
</td>
</tr>
<tr>
<td class="journal">
[J-20] Journal of Computer and System Sciences <b> JCSS </b> Volume 156:103724 (2026).
</td>
</tr>
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p26">Summary</a> |
<a href="https://arxiv.org/abs/2403.06290" target="_blank">Paper</a> | <a href="./docs/2024-WG-Presentation.pdf" target="_blank" class="summary-link">Presentation by V. K. Kutty Malu </a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p26" class="collapse">
We present an improved fixed parameter tractable
algorithms for both of these problems.
We also prove that Path Contraction is polynomial
time solvable on planar graphs and on chordal
graphs,
it admits a polynomial time algorithm which i
optimal
under Orthogonal Vector Conjecture.
</p>
</div>
</div>
<br/>
<div class="bibentry-article">
<div>
<table>
<tr><td class="paper">[ P-25 ] Conflict and Fairness in Resource Allocation</td>
</tr>
<tr>
<td> with <i> Susobhan Bandopadhyay, Aritra Banik, Sushmita Gupta, Pallavi Jain, Abhishek Sahu, Saket Saurabh </i></td>
</tr>
<!--tr>
<td class="conference">
[C-XX] Conference.
</td>
</tr-->
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p25">Summary</a>|
<a href="https://arxiv.org/abs/2403.04265" target="_blank">Paper</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p25" class="collapse">
We study parameterized complexity of a fair allocation
problem in which we are given a set of agents,
a set of resources, a utility function for every
agent over a set of resources, and a conflict graph on
the set of resources (where an edge denotes
incompatibility).
The goal is to assign resources to the agents such that
(i) the set of resources allocated to an agent
are compatible with each other, and
(ii) the minimum satisfaction of an agent is maximized.
</p>
</div>
</div>
<br/>
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-24 ] Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction </td>
</tr>
<tr>
<td> with <i> R. Krithika, V. K. Kutty Malu, and Roohani Sharma </i></td>
</tr>
<tr>
<td class="conference">
[C-22] Foundations of Software Technology and Theoretical Computer Science, <b>FSTTCS</b> 2023.
</td>
</tr>
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p24">Summary</a> |
<a href="https://arxiv.org/abs/2307.10607" target="_blank">Paper</a> | <a href="./docs/2023-FSTTCS-slides.pdf" target="_blank" class="summary-link">Presentation by V. K. Kutty Malu </a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p24" class="collapse">
In this work, we initiate the complexity study of Biclique Contraction
and Balanced Biclique Contraction.
We first prove that these problems are NP-complete, admit simple
single exponential algorithms,
but differ in their kernelization complexity.
</p>
</div>
</div>
<br/>
<div class="bibentry-journal">
<div>
<table>
<tr><td class="paper">[ P-23 ] Romeo and Juliet Meeting in Forest Like Regions </td>
</tr>
<tr>
<td> with <i> Neeldhara Misra, Manas Mulpuri, and Gaurav Viramgami </i></td>
</tr>
<tr>
<td class="conference">
[C-21] Foundations of Software Technology and Theoretical Computer Science, <b>FSTTCS</b> 2022.
</td>
</tr>
<tr>
<td class="journal">
[J-19] Algorithmica Volumne 86(11): 3465-3495 (2024).
</td>
</tr>
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p23">Summary</a> |
<a href="https://arxiv.org/abs/2210.02582" target="_blank">Paper</a> |
<a href="./docs/2022-FSTTCS-Presentation.pdf" target="_blank">Presentation by G. Viramgami</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p23" class="collapse">
The game of rendezvous with adversaries is a game on a graph played by two players:
Facilitator and Divider. Facilitator has two agents and Divider has a team of k agents.
While the initial positions of Facilitator’s agents are fixed,
Divider gets to select the initial positions of his agents.
Then, they take turns to move their agents to adjacent vertices (or stay put)
with Facilitator’s goal
to bring both her agents at same vertex and Divider’s goal to prevent it.
The computational question of interest is to determine if Facilitator
has a winning strategy against Divider with k agents.
In this work, we prove that this problem is hard even when the graph is very close to a forest.
</p>
</div>
</div>
<br/>
<div class="bibentry-journal">
<div>
<table>
<tr><td class="paper">[ P-22 ] Domination and Cut Problems on Chordal Graphs with Bounded Leafage. </td>
</tr>
<tr>
<td> with <i> Esther Galby, Daniel Marx, Philipp Schepper, and Roohani Sharma. </i></td>
</tr>
<tr>
<td class="conference">
[ C-20 ] International Symposium on Parameterized and Exact Computation, <b>IPEC</b> 2022.
</td>
</tr>
<tr>
<td class="journal">
[J-18] Algorithmica, Valume 86 (5): 1428-1474 (2024).
</td>
</tr>
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p22">Summary</a> |
<a href="https://arxiv.org/abs/2208.02850" target="_blank">Paper</a> |
<a href="./docs/2022-IPEC-Slides.pdf" target="_blank"> Presentation by R. Sharma</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p22" class="collapse">
The leafage of a chordal graph G is the minimum integer l such that G
can be realized as an
intersection graph of subtrees of a tree with l leaves.
We consider structural parameterization by
the leafage of classical problems like DOMINATING SET, MULTI-CUT, STEINER-TREE on chordal graphs.
We also prove that MULTIWAY CUT with Undeletable Terminals
on chordal graphs can be solved in polynomial time.
</p>
</div>
</div>
<br/>
<div class="bibentry-journal">
<div>
<table>
<tr> <td class="paper">
[ P-21 ] Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters.
</td>
</tr>
<tr>
<td> <i>with </i> Esther Galby, Liana Khazaliya, Fionn Mc Inerney, and Roohani Sharma.</td>
</tr>
<tr>
<td class="conference">
[ C-19 ] Mathematical Foundations of Computer Science, <b>MFCS</b> 2022.
</td>
</tr>
<tr>
<td class="journal">
[ J-17 ] SIAM Journal on Discrete Mathematics, <b>SIDMA</b>,
Volume 37 (4): 2241-2264 (2023).
</td>
</tr>
<td><a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-j21">Summary</a> |
<a href="https://arxiv.org/abs/2206.15424" target="_blank">Paper</a> |
<a href="./docs/2022-MFCS-slides.pdf" target="_blank">Presentation by L. Khazaliya</a>
</td>
<tr>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-j21" class="collapse">
For a graph G, a subset S of V (G) is called a resolving set if for
any two vertices u, v in V(G), there
is a vertex w in S such that dist(u, w) is not equal to dist(v, w).
The METRIC DIMENSTION problem ask whether there exists a resolving set
of size at most k in the given graph.
In this article, we advance our understanding of structural
parameterization of the problem.
</p>
</div>
</div>
<br/>
<div class="bibentry-journal">
<div>
<table>
<tr><td class="paper"> [ P-20 ] Reducing the Vertex Cover Number via Edge Contractions. </td>
</tr>
<tr>
<td> with <i> Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, and Ueverton S. Souza. </i></td>
</tr>
<tr>
<td class="conference">
[ C-18 ] Mathematical Foundations of Computer Science, <b>MFCS</b> 2022.
</td>
</tr>
<tr>
<td class="journal">
[ J-16 ] Journal of Computer and System Sciences <b> JCSS </b> Volume 129: 22-38 (2022).
</td>
</tr>
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p20">Summary</a> |
<a href="https://arxiv.org/abs/2202.03322" target="_blank">Paper</a> |
<a href="./docs/2022-MFCS-VC-slides.pdf" target="_blank">Presentation by U. Souza </a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p20" class="collapse">
The CONTRACTION(vc) problem takes as input a graph G on
n vertices and two integers k and d, and
asks whether one can contract at most
k edges to reduce the size of a minimum vertex cover of G by
at least d. Recently, Lima et al. [JCSS 2021] proved
that unlike most of the so-called blocker problems,
CONTRACTION(vc) admits an XP algorithm.
They left open the question of whether this problem is FPT
under the standard parameterization.
We answer this question in negative and prove some othe
results.
</p>
</div>
</div>
<br/>
<div class="bibentry-journal">
<div>
<table>
<tr><td class="paper">[ P-19 ] Parameterized Complexity of Weighted Multicut in Trees. </td>
</tr>
<tr>
<td> with <i> Esther Galby, Daniel Marx, Philipp Schepper, and Roohani Sharma. </i></td>
</tr>
<tr>
<td class="conference">
[ C-17 ] Workshop on Graph-Theoretic Concepts in Computer Science, <b>WG</b> 2022.
</td>
</tr>
<tr>
<td class="journal">
[ J-15 ] Theoretical Computer Science, <b> TCS </b>, Volume 978: 114174, 2023.
</td>
</tr>
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p19">Summary</a> |
<a href="https://arxiv.org/pdf/2205.10105" target="_blank">Paper</a> |
<a href="./docs/2022-WG-WMT-slides.pdf" target="_blank">Presentation by P. Schepper</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p19" class="collapse">
The Multicut problem is a classical cut problem
where given an undirected graph G, a set of pairs of
vertices P, and a budget k.
The goal is to determine if there is a set S of
at most k edges such that for each (s,t) in P,
G - S has no path from s to t.
In the weighted version of the problem, one is additionally
given a weight function, the goal is to determine if there is
a solution of size at most k and weight at most w.
Bousquet et al. [STACS 2009] asked whether Weighted Multicut
on trees is FPT.
In this article, we answer this question positively
by designing an algorithm using a very recent technique of
directed flow augmentation by Kim et al. [STOC 2022].
</p>
</div>
</div>
<br/>
<div class="bibentry-journal">
<div>
<table>
<tr><td class="paper">[ P-18 ] The Complexity of Contracting Bipartite Graphs into Small Cycles. </td>
</tr>
<tr>
<td> with <i> R. Krithika, and Roohani Sharma. </i></td>
</tr>
<tr>
<td class="conference">
[ C-16 ] Workshop on Graph-Theoretic Concepts in Computer Science, <b>WG</b> 2022.
</td>
</tr>
<tr>
<td class="journal">
[J-14] (To appear) Discrete Mathematics and Theoretical Computer Science <b> DMTCS </b>, 2025.
</td>
</tr>
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p18">Summary</a> |
<a href="https://arxiv.org/abs/2206.07358" target="_blank">Paper</a> |
<a href="./docs/2022-WG-slides.pdf" target="_blank">Presentation</a>
</td>
</tr>
</table>
</div>
<div class="summary-details">
<p id="summary-p18" class="collapse">
The C_q-Contractibility problem takes
as input an undirected simple graph G and determines whether G
can be
transformed into C_q (the induced cycle on q vertices)
using only edge contractions.
In this paper, we show that both C_5-Contractibility and C_4-
Contractibility are NP-complete on bipartite graphs.
This completes a dichotomy results and answers open questions
stated in Dabrowski and Paulusma [IPL 2017].
</p>
</div>
</div>
<p><small><i>Mr. Sumit Kumar Prajapati, a student of IIT-Jodhpur,
made this <a href="https://youtu.be/93FTho2PllI"
target="_blank">video presentation</a>
independently as a part of his course project.
</i></small>
</p>
<br/>
<div class="bibentry-conference">
<div>
<table>
<tr><td class="paper">[ P-17 ] A Framework for Parameterized
Subexponential Algorithms
for Generalized Cycle Hitting Problems on Planar Graphs. </td>
</tr>
<tr>
<td> with <i> Daniel Marx, Pranabendu Misra, and Daniel Neuen. </i></td>
</tr>
<tr>
<td class="conference">
[ C-15 ] ACM-SIAM Symposium on Discrete Algorithms, <b>SODA</b> 2022.
</td>
</tr>
<!--tr>
<td class="journal">
[J-XX] Journal.
</td>
</tr-->
<tr>
<td> <a style="cursor: pointer;" data-toggle="collapse" data-target="#summary-p17">Summary</a> |
<a href="https://arxiv.org/abs/2110.15098" target="_blank">Paper</a> |
<a href="./docs/2022-SODA-slides.pdf" target="_blank">Presentation by Daniel Neuen </a>
</td>
</tr>
</table>
</div>
<div class="summary-details">