4 papers
The Parameterised Complexity of Temporal Motif Counting, and a Lovász-Style Isomorphism Theorem
Jayakrishnan Madathil, Kitty Meeks, Marc Roth
We study the structural expressivity and the parameterised complexity of counting homomorphisms from small temporal patterns to large temporal graphs. Here, a temporal pattern …
Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
Sheikh Shakil Akhtar, Jayakrishnan Madathil, Pranabendu Misra +1
A typical goal of research in combinatorial optimization is to come up with fast algorithms that find optimal solutions to a computational problem. The process that takes a real-wo…
Temporal Triadic Closure: Finding Dense Structures in Social Networks That Evolve
Tom Davot, Jessica Enright, Jayakrishnan Madathil +1
A graph G is c-closed if every two vertices with at least c common neighbors are adjacent to each other. Introduced by Fox, Roughgarden, Seshadhri, Wei and Wein [ICALP 2018, SICOMP…
The Cost and Complexity of Minimizing Envy in House Allocation
Jayakrishnan Madathil, Neeldhara Misra, Aditi Sethia
We study almost-envy-freeness in house allocation, where houses are to be allocated among agents so that every agent receives exactly one house. An envy-free allocation nee…