Arrow Research search

Author name cluster

Ignaz Rutter

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
2 author rows

Possible papers

20

AAAI Conference 2023 Conference Paper

The Influence of Dimensions on the Complexity of Computing Decision Trees

  • Stephen G. Kobourov
  • Maarten Löffler
  • Fabrizio Montecchiani
  • Marcin Pilipczuk
  • Ignaz Rutter
  • Raimund Seidel
  • Manuel Sorge
  • Jules Wulms

A decision tree recursively splits a feature space \mathbb{R}^d and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space \mathbb{R}^d, which contains n training examples. We show that it can be solved in O(n^(2d + 1)) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d) * n^o(d / log d) running time. The problem is solvable in (dR)^O(dR) * n^(1+o(1)) time, if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

PDF Details DOI

MFCS Conference 2022 Conference Paper

Extending Partial Representations of Circle Graphs in Near-Linear Time

  • Guido Brückner
  • Ignaz Rutter
  • Peter Stumpf

The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph H ⊆ G and a representation H of H. The question is whether G admits a representation G whose restriction to H is H. We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams. We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in O((n + m) α(n + m)) time, where α is the inverse Ackermann function. This improves over an O(n³)-time algorithm by Chaplick, Fulek and Klavík [2019]. The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.

Details

TCS Journal 2018 Journal Article

Gap-planar graphs

  • Sang Won Bae
  • Jean-Francois Baffier
  • Jinhee Chun
  • Peter Eades
  • Kord Eickmeyer
  • Luca Grilli
  • Seok-Hee Hong
  • Matias Korman
Details DOI

SODA Conference 2017 Conference Paper

Partial and Constrained Level Planarity

  • Guido Brückner
  • Ignaz Rutter

Let G = ( V, E ) be a directed graph and ℓ: V → [ k ]: = {1, …, k } a level assignment such that ℓ ( u ) < ℓ ( v ) for all directed edges ( u, v ) ∊ E. A level planar drawing of G is a drawing of G where each vertex v is mapped to a unique point on the horizontal line íj with y -coordinate í( v ), and each edge is drawn as a y -monotone curve between its endpoints such that no two curves cross in their interior. In the problem C onstrained L evel P lanarity (CLP for short), we are further given a partial ordering of V i: = ℓ −1 ( i ) for i ∊ [ k ], and we seek a level planar drawing where the order of the vertices on ℓ i is a linear extension of A special case of this is the problem P artial L evel P lanarity (PLP for short), where we are asked to extend a given level-planar drawing H of a subgraph H ⊆ G to a complete drawing G of G without modifying the given drawing, i. e. , the restriction of G to H must coincide with H. We give a simple polynomial-time algorithm with running time O ( n 5 ) for CLP of single-source graphs that is based on a simplified version of an existing level- planarity testing algorithm for single-source graphs. We introduce a modified type of PQ-tree data structure that is capable of efficiently handling the arising constraints to improve the running time to O ( n + kℓ ), where ℓ is the size of the constraints. We complement this result by showing that PLP is NP-complete even in very restricted cases. In particular, PLP remains NP- complete even when G is a subdivision of a triconnected planar graph with bounded degree.

Details

SODA Conference 2013 Conference Paper

Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems

  • Thomas Bläsius
  • Ignaz Rutter

In this paper, we define and study the new problem S imultaneous PQ-O rdering. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. S imultaneous PQ-O rdering asks whether orders of the leaves of each of the trees can be chosen simultaneously, that is, for every child-parent relation the order chosen for the parent is an extension of the order chosen for the child. We show that S imultaneous PQ-O rdering is -complete in general and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of S imultaneous PQ-O rdering. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for P artially PQ-C onstrained P lanarity for biconnected graphs, which asks for a planar embedding in the presence of PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for S imultaneous E mbedding with F ixed E dges for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two non-trivial blocks. This includes for example the case where both graphs have maximum degree 5.

Details