8 papers · 1 filter
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…