Viser treff 21-35 av 35

• #### Parameterization Above a Multiplicative Guarantee ﻿

(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 complexity classification of deletion to list matrix-partition for low-order matrices ﻿

(Journal article; Peer reviewed, 2019)
Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G) - > 2^{[l]} (where [l] = {1,2,...,l}), a list M-partition of G with respect to L is a partition of V(G) into l parts, ...
• #### Parameterized complexity of conflict-free matchings and paths ﻿

(Journal article; Peer reviewed, 2019)
An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) ...
• #### Parameterized Complexity of Directed Spanner Problems ﻿

(Journal article; Peer reviewed, 2020)
We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...
• #### The Parameterized Complexity of Guarding Almost Convex Polygons ﻿

(Journal article; Peer reviewed, 2020)
The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide ...
• #### Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ﻿

(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 ...
• #### Parameterized streaming algorithms for min-ones d-SAT ﻿

(Journal article; Peer reviewed, 2019)
In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has ...
• #### Path contraction faster than $2^n$ ﻿

(Journal article; Peer reviewed, 2020)
A graph $G$ is contractible to a graph $H$ if there is a set $X \subseteq E(G)$, such that $G/X$ is isomorphic to $H$. Here, $G/X$ is the graph obtained from $G$ by contracting all the edges in $X$. For a family of graphs ...
• #### Path Contraction Faster Than 2n ﻿

(Peer reviewed; Journal article, 2019)
A graph G is contractible to a graph H if there is a set X subseteq E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the F-Contraction ...
• #### A Polynomial Kernel for Paw-Free Editing ﻿

(Journal article; Peer reviewed, 2020)
For a fixed graph H, the H-free Edge Editing problem asks whether we can modify a given graph G by adding or deleting at most k edges such that the resulting graph does not contain H as an induced subgraph. The problem is ...
• #### Quick but odd growth of cacti ﻿

(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 ﻿

(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 ﻿

(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 ...
• #### Subexponential Algorithms for Partial Cover Problems ﻿

(Conference object; Peer reviewed; Journal article, 2009)
Partial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or ...
• #### Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems ﻿

(Peer reviewed; Journal article, 2019)
We consider four well-studied NP-complete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3-Packing. For ...