Browsing Bergen Open Research Archive by Author "Panolan, Fahad"
Now showing items 117 of 17

A (2 + ε)Factor Approximation Algorithm for Split Vertex Deletion
Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2020)In the Split Vertex Deletion (SVD) problem, the input is an nvertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that GS is a split graph ... 
Bchromatic number: Beyond NPhardness
Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Peer reviewed; Journal article, 2015)The bchromatic number of a graph G, chi_b(G), is the largest integer k such that G has a kvertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ... 
Complexity of the Steiner Network Problem with Respect to the Number of Terminals
Eiben, Eduard; Knop, Dusan; Panolan, Fahad; Suchý, Ondřej (Journal article; Peer reviewed, 2019)In the Directed Steiner Network problem we are given an arcweighted digraph G, a set of terminals T subseteq V(G) with T=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H ... 
Decomposition of map graphs with applications
Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 2019) 
Diverse Collections in Matroids and Graphs
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2021)We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse ... 
Diverse collections in matroids and graphs
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2023)We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid M, a weight function ω : ... 
ETHtight algorithms for long path and cycle on unit disk graphs
Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(√k)(n + m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs ... 
Finding even subgraphs even faster
Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Peer reviewed; Journal article, 2015)Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k ... 
Going Far from Degeneracy
Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)An undirected graph $G$ is $d$degenerate if every subgraph of $G$ has a vertex of degree at most $d$. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy $d>1$ contains a cycle of length at ... 
Going Far From Degeneracy
Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 20190906)An undirected graph G is ddegenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erd\H{o}s and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least ... 
LowRank Binary Matrix Approximation in ColumnSum Norm
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Journal article; Peer reviewed, 2020)We consider 𝓁₁Rankr Approximation over {GF}(2), where for a binary m× n matrix 𝐀 and a positive integer constant r, one seeks a binary matrix 𝐁 of rank at most r, minimizing the columnsum norm ‖ 𝐀 𝐁‖₁. We show ... 
Parameterization Above a Multiplicative Guarantee
Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixedparameter tractable problems in this paradigm share an additive form defined as follows. Given ... 
Parameterized SingleExponential Time Polynomial Space Algorithm for Steiner Tree
Fomin, Fedor; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (Peer reviewed; Journal article, 2019)In the Steiner Tree problem, we are given as input a connected \(n\)vertex graph with edge weights in \(\{1,2,\ldots,W\}\), and a set of \(k\) terminal vertices. Our task is to compute a minimumweight tree that contains ... 
Quick but odd growth of cacti
Kolay, Sudeshna; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (Peer reviewed; Journal article, 2015)Let F be a family of graphs. Given an input graph G and a positive integer k, testing whether G has a ksized subset of vertices S, such that G\S belongs to F, is a prototype vertex deletion problem. These type of problems ... 
Quick separation in chordal and split graphs
Misra, Pranabendu; Panolan, Fahad; Rai, Ashutosh; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2020)In this paper we study two classical cut problems, namely Multicut and Multiway Cut on chordal graphs and split graphs. In the Multicut problem, the input is a graph G, a collection of 𝓁 vertex pairs (si, ti), i ∈ [𝓁], ... 
Rank vertex cover as a natural problem for algebraic compression
Meesum, Syed Mohammad; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a longstanding, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and ... 
Refined Complexity of PCA with Outliers
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Peer reviewed; Journal article, 2019)Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance and bioinformatics to image analysis and ...