8 papers
Not All Degree Constraints Are Created Equal when Computing Spanning Trees
Narek Bojikian, Alexander Firbas, Robert Ganian +2
We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share…
Tight bounds for clique-packing parameterized by clique-width
Narek Bojikian, Stefan Kratsch
In the -Clique Packing problem, given a graph and an integer , we need to decide whether contains a set of pairwise vertex-disjoint cliques of size each. This…
Tight Bounds for Feedback Vertex Set Parameterized by Clique-width
Narek Bojikian, Stefan Kratsch
We introduce a new notion of acyclicity representation in labeled graphs, and present three applications thereof. Our main result is an algorithm that, given a graph and a -…
Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
Narek Bojikian, Alexander Firbas, Robert Ganian +2
We investigate the computation of minimum-cost spanning trees satisfying prescribed vertex degree constraints: Given a graph and a constraint function , we ask for a (minimu…
Tight Bounds for some Classical Problems Parameterized by Cutwidth
Narek Bojikian, Vera Chekan, Stefan Kratsch
Cutwidth is a widely studied parameter that quantifies how well a graph can be decomposed along small edge-cuts. It complements pathwidth, which captures decomposition by small ver…
Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
Narek Bojikian, Stefan Kratsch
Recently, Bojikian and Kratsch [2023] have presented a novel approach to tackle connectivity problems parameterized by clique-width (), based on counting small r…
A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
Narek Bojikian, Stefan Kratsch
Recently, Hegerfeld and Kratsch [ESA 2023] obtained the first tight algorithmic results for hard connectivity problems parameterized by clique-width. Concretely, they gave one-side…
Tight Bounds for Connectivity Problems Parameterized by Cutwidth
Narek Bojikian, Vera Chekan, Falko Hegerfeld +1
In this work we start the investigation of tight complexity bounds for connectivity problems parameterized by cutwidth assuming the Strong Exponential-Time Hypothesis (SETH). Van G…