Browsing Faculty of Mathematics and Natural Sciences by Journals "Algorithmica"

Now showing items 1-9 of 9

    • A Fixed-Parameter Perspective on #BIS 

      Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (Peer reviewed; Journal article, 2019-07-18)
      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 ...

    • Mim-Width II. The Feedback Vertex Set Problem 

      Jaffke, Lars; Kwon, O-Joung; Telle, Jan Arne (Peer reviewed; Journal article, 2020)
      We give a first polynomial-time algorithm for (WEIGHTED) FEEDBACK VERTEX SET on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an nO(w)-time ...

    • On cutwidth parameterized by vertex cover 

      Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Saurabh, Saket (Peer reviewed; Journal article, 2014-04)
      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 H-Graphs 

      Fomin, Fedor; Golovach, Petr; Raymond, Jean-Florent (Journal article; Peer reviewed, 2020)
      For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc ...

    • Parameterized complexity of Eulerian deletion problems 

      Cygan, Marek; Pilipczuk, Marcin; Marx, Dániel; Pilipczuk, Michal Pawel; Schlotter, Ildikó (Peer reviewed; Journal article, 2014-01)
      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 

      Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr; Otachi, Yota; van Leeuwen, Erik Jan (Peer reviewed; Journal article, 2012-09)
      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 apex-minor-free graphs, a general class ...

    • Solving the 2-disjoint connected subgraphs problem faster than 2ⁿ 

      Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Wojtaszczyk, Jakub Onufry (Peer reviewed; Journal article, 2014-10)
      The 2-DISJOINT 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 

      Fomin, Fedor; Golovach, Petr; Strømme, Torstein J. F.; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2020-02)
      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 

      Bergougnoux, Benjamin; Eiben, Eduard; Ganian, Robert; Ordyniak, Sebastian; Ramanujan, M. S. (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. ...