• Bisection of Bounded Treewidth Graphs by Convolutions 

      Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E. (Journal article; Peer reviewed, 2019)
      In the Bisection problem, we are given as input an edge-weighted graph G. The task is to find a partition of V(G) into two parts A and B such that ||A| - |B|| <= 1 and the sum of the weights of the edges with one endpoint ...
    • 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 ...
    • A Polynomial Kernel for Line Graph Deletion 

      Lochet, William; Eiben, Eduard (Journal article; Peer reviewed, 2020)
      The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f ∈ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some ...
    • A Polynomial Kernel for Paw-Free Editing 

      Eiben, Eduard; Lochet, William; Saurabh, Saket (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 ...
    • 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. ...
    • A Unifying Framework for Characterizing and Computing Width Measures 

      Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Jaffke, Lars; Kwon, O-joung (Journal article; Peer reviewed, 2022)
      Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, ...