Home
Hasso-Plattner-Institut
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

schließen

schließen

schließen

schließen

schließen

schließen

schließen

schließen
  1. soda-gd-isaac

30.10.2023

Three Papers accepted at SODA, GD and ISAAC

Recently, our group had three more accepted papers: The first paper, Tree Containment Above Minimum Degree is FPT was accepted at the Symposium on Discrete Algorithms (SODA) taking place in Alexandria, USA on 7-10 January 2024. By a classical Chvátal’s Lemma, a graph of minimum degree \(δ(G)\) contains every tree on \(δ(G) + 1\) vertices. The paper's main result is the following algorithmic “extension” of Chvátal’s Lemma: For any \(n\)-vertex graph \(G\), integer \(k\), and a tree \(T\) on at most \(δ(G) + k\) vertices, deciding whether \(G\) contains a subgraph isomorphic to \(T\) can be done in time \(f(k) · poly(n)\) for some function \(f\) of \(k\) only.

At the International Symposium on Graph Drawing and Network Visualization (GD) which took place in Isola delle Femmine, Italy on 20-22 September the paper Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth was accepted. Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing; both are known to be NP-complete, but admit algorithms with running time \(n^O(tw)\), where tw is the treewidth of the input graph. In this paper, the authors show that these algorithms are essentially optimal and cannot be improved, up to standard complexity assumptions.

Finally, there is also the paper The st-Planar Edge Completion Problem is Fixed-Parameter Tractable which was accepted at the International Symposium on Algorithms and Computation (ISAAC) which will take place on 3-6 December in Kyoto, Japan. The problem of deciding whether a biconnected planar digraph \(G\) can be augmented to an st-planar graph by adding a set of oriented edges, closely related to Upward Planarity testing, is known to be NP-complete. The paper's authors show that the problem is fixed-parameter tractable when parameterized by the number of edges to add.

  • Tree Containment Above Mi... - Download
    Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill Tree Containment Above Minimum Degree is FPTSymposium on Discrete Algorithms (SODA) 2024: 366–376
    [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
     
  • Upward and Orthogonal Pla... - Download
    Jansen, Bart M. P.; Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, Kirill Upward and Orthogonal Planarity are W[1]-Hard Parameterized by TreewidthGraph Drawing (GD) 2023: 203–217
    [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
     
  • The st-Planar Edge Comple... - Download
    Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, Kirill The st-Planar Edge Completion Problem Is Fixed-Parameter TractableInternational Symposium Algorithms and Computation (ISAAC) 2023: 46:1–46:13
    [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]