1 citations · 1 across the 11 of their papers we have counts for
13 papers
Odd Cycle Transversal on -free graphs
Esther Galby, Paloma T. de Lima, Andrea Munaro +1
\textsc{Odd Cycle Transversal} is a classic -hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite…
Induced packing treewidth II. Excluding a clique or a biclique
Amir Nikabadi, Paweł Rzążewski
The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured t…
A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability
Radu Curticapean, Daniel Neuen, Amir Nikabadi +2
Two graphs and are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph in . A wide…
Induced packing treewidth
Amir Nikabadi, Paweł Rzążewski
In this paper, we introduce a framework that aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structu…
Counting equitable -colorings in graphs of bounded clique-width
Holger Dell, Thore Husfeldt, Amir Nikabadi
For a graph , a proper -coloring of is \emph{equitable} if the sizes of any two color classes differ by at most one. The \textsc{Equitable -Coloring} problem asks, for…
Clique-width and induced topological minors
Paweł Rafał Bieliński, Jadwiga Czyżewska, Martin Milanič +2
A is a chordless path on four vertices. A diamond is a graph obtained from a clique of size four by removing one edge of the clique. A paw is a graph obtained from a clique o…
The Gallai Vertex Problem is -Complete
Amir Nikabadi, Eva Rotenberg, Lasse Wulf
When a graph admits a vertex that is contained in all its longest paths, we call a Gallai vertex. These are named after Gallai, who in 1966 asked the question if it is…
Equitable coloring of large bipartite graphs
Amir Nikabadi
For a graph , the \emph{equitable chromatic number} of , denoted by , is the smallest integer such that admits a proper -coloring whose color classes diffe…
Hitting all longest paths in -free graphs and -graphs
Paloma T. de Lima, Amir Nikabadi, Paweł Rzążewski
The \textit{longest path transversal number} of a connected graph , denoted by , is the minimum size of a set of vertices of that intersects all longest paths in …
Maximum list -colorable induced subgraphs in -free graphs
Esther Galby, Paloma T. Lima, Andrea Munaro +1
We show that, for every fixed positive integers and , \textsc{Max-Weight List -Colorable Induced Subgraph} admits a polynomial-time algorithm on -free graphs. This…
Non-empty intersection of longest paths in -free and claw-free graphs
Paloma T. Lima, Amir Nikabadi
A family of graphs is a \textit{Gallai family} if for every connected graph , all longest paths in have a common vertex. While it is not known w…
Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters
Janne H. Korhonen, Amir Nikabadi
Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems c…
On the Parameterized Complexity of Sparsest Cut and Small-set Expansion Problems
Ramin Javadi, Amir Nikabadi
We present a parameterized dichotomy for the \textsc{-Sparsest Cut} problem in weighted and unweighted versions. In particular, we show that the weighted \textsc{-Sparsest Cu…