Browsing Bergen Open Research Archive by Author "Panolan, Fahad"

Now showing items 1-15 of 15

    • 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 n-vertex 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 G-S is a split graph ...

    • B-chromatic number: Beyond NP-hardness 

      Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Conference object; Peer reviewed; Journal article, 2015)
      The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex 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 arc-weighted 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)

    • ETH-tight 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 (Conference object; 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, 2019-09-06)
      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\H{o}s and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least ...

    • Low-Rank Binary Matrix Approximation in Column-Sum Norm 

      Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Journal article; Peer reviewed, 2020)
      We consider 𝓁₁-Rank-r 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 column-sum 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 fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given ...

    • Parameterized Single-Exponential 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 minimum-weight tree that contains ...

    • Quick but odd growth of cacti 

      Kolay, Sudeshna; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (Conference object; 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 k-sized 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 long-standing, 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 (Conference object; 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 ...