• Compressing permutation groups into grammars and polytopes. A graph embedding approach 

      Jaffke, Lars; De Oliveira Oliveira, Mateus; Tiwary, Hans Raj (Journal article; Peer reviewed, 2020)
      It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can ...
    • On the Satisfiability of Smooth Grid CSPs 

      De Oliveira Oliveira, Mateus; Alferov, Vasily (Journal article; Peer reviewed, 2022)
      Many important NP-hard problems, arising in a wide variety of contexts, can be reduced straightforwardly to the satisfiability problem for CSPs whose underlying graph is a grid. In this work, we push forward the study of ...
    • Synthesis and Analysis of Petri Nets from Causal Specifications 

      De Oliveira Oliveira, Mateus (Journal article; Peer reviewed, 2022)
      Petri nets are one of the most prominent system-level formalisms for the specification of causality in concurrent, distributed, or multi-agent systems. This formalism is abstract enough to be analyzed using theoretical ...
    • Three Is Enough for Steiner Trees 

      Arrighi, Emmanuel; De Oliveira Oliveira, Mateus (Journal article; Peer reviewed, 2021)
      In the Steiner tree problem, the input consists of an edge-weighted graph G together with a set S of terminal vertices. The goal is to find a minimum weight tree in G that spans all terminals. This fundamental NP-hard ...
    • Width Notions for Ordering-Related Problems 

      Arrighi, Emmanuel; Fernau, Henning; De Oliveira Oliveira, Mateus; Wolf, Petra (Journal article; Peer reviewed, 2020)
      We are studying a weighted version of a linear extension problem, given some finite partial order ρ, called Completion of an Ordering. While this problem is NP-complete, we show that it lies in FPT when parameterized by ...