Browsing Faculty of Mathematics and Natural Sciences by Journals "Algorithmica"
Now showing items 19 of 9

A FixedParameter Perspective on #BIS
(Peer reviewed; Journal article, 20190718)The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHΠ1. It is believed that #BIS ... 
MimWidth II. The Feedback Vertex Set Problem
(Peer reviewed; Journal article, 2020)We give a first polynomialtime algorithm for (WEIGHTED) FEEDBACK VERTEX SET on graphs of bounded maximum induced matching width (mimwidth). Explicitly, given a branch decomposition of mimwidth w, we give an nO(w)time ... 
On cutwidth parameterized by vertex cover
(Peer reviewed; Journal article, 201404)We study the CUTWIDTH problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two ... 
On the Tractability of Optimization Problems on HGraphs
(Journal article; Peer reviewed, 2020)For a graph H, a graph G is an Hgraph if it is an intersection graph of connected subgraphs of some subdivision of H. Hgraphs naturally generalize several important graph classes like interval graphs or circulararc ... 
Parameterized complexity of Eulerian deletion problems
(Peer reviewed; Journal article, 201401)We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity ... 
Parameterized complexity of the spanning tree congestion problem
(Peer reviewed; Journal article, 201209)We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apexminorfree graphs, a general class ... 
Solving the 2disjoint connected subgraphs problem faster than 2ⁿ
(Peer reviewed; Journal article, 201410)The 2DISJOINT CONNECTED SUBGRAPHS problem, given a graph along with two disjoint sets of terminals Z1,Z2, asks whether it is possible to find disjoint sets A1,A2, such that Z1 ⊆ A1, Z2 ⊆ A2 and A1,A2 induce connected ... 
Subgraph Complementation
(Journal article; Peer reviewed, 202002)A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there ... 
Towards a Polynomial Kernel for Directed Feedback Vertex Set
(Journal article; Peer reviewed, 2020)In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. ...