Browsing Department of Informatics by Journals "Leibniz International Proceedings in Informatics"
Now showing items 41-60 of 97
-
FPT Approximation for Fair Minimum-Load Clustering
(Journal article; Peer reviewed, 2022)In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of ... -
Going Far From Degeneracy
(Peer reviewed; Journal article, 2019-09-06)An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erd\H{o}s and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least ... -
Hierarchical clusterings of unweighted graphs
(Journal article; Peer reviewed, 2020)We study the complexity of finding an optimal hierarchical clustering of an unweighted similarity graph under the recently introduced Dasgupta objective function. We introduce a proof technique, called the normalization ... -
Investigating Streamless Sets
(Journal article; Peer reviewed, 2015)In this paper we look at streamless sets, recently investigated by Coquand and Spiwack. A set is streamless if every stream over that set contain a duplicate. It is an open question in constructive mathematics whether the ... -
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
(Peer reviewed; Journal article, 2009)The {\sc \(k\)-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least \(k\) leaves in a given digraph. The problem has recently received much attention from the ... -
Kernelization of Whitney Switches
(Journal article; Peer reviewed, 2020)A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations ... -
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms
(Journal article; Peer reviewed, 2022)We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree ... -
Longest Cycle Above Erdös-Gallai Bound
(Journal article; Peer reviewed, 2022)In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2^𝒪(k)⋅n^𝒪(1) decides whether a 2-connected ... -
Low-Rank Binary Matrix Approximation in Column-Sum Norm
(Journal article; Peer reviewed, 2020)We consider 𝓁₁-Rank-r Approximation over {GF}(2), where for a binary m× n matrix 𝐀 and a positive integer constant r, one seeks a binary matrix 𝐁 of rank at most r, minimizing the column-sum norm ‖ 𝐀 -𝐁‖₁. We show ... -
Maximum matching width: New characterizations and a fast algorithm for dominating set
(Peer reviewed; Journal article, 2015)We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A ... -
Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
(Peer reviewed; Journal article, 2011)The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop ... -
A Model of Type Theory in Cubical Sets
(Peer reviewed; Journal article, 2014)We present a model of type theory with dependent product, sum, and identity, in cubical sets. We describe a universe and explain how to transform an equivalence between two types into an equality. We also explain how to ... -
Modification to planarity is fixed parameter tractable
(Peer reviewed; Journal article, 2019)A replacement action is a function L that maps each k-vertex labeled graph to another k-vertex graph. We consider a general family of graph modification problems, called L-Replacement to C, where the input is a graph G and ... -
Non-Constructivity in Kan Simplicial Sets
(Journal article; Peer reviewed, 2015)We give an analysis of the non-constructivity of the following basic result: if X and Y are simplicial sets and Y has the Kan extension property, then Y X also has the Kan extension property. By means of Kripke countermodels ... -
Non-Uniform k-Center and Greedy Clustering
(Journal article; Peer reviewed, 2022)In the Non-Uniform k-Center (NUkC) problem, a generalization of the famous k-center clustering problem, we want to cover the given set of points in a metric space by finding a placement of balls with specified radii. In ... -
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
(Journal article; Peer reviewed, 2021)In the Intersection Non-emptiness problem, we are given a list of finite automata A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine whether some string w ∈ Σ^* lies in the intersection of the ... -
On the Complexity of Recovering Incidence Matrices
(Journal article; Peer reviewed, 2020)The incidence matrix of a graph is a fundamental object naturally appearing in many applications, involving graphs such as social networks, communication networks, or transportation networks. Often, the data collected about ... -
On the Hardness of Generalized Domination Problems Parameterized by Mim-Width
(Journal article; Peer reviewed, 2022)For nonempty σ, ρ ⊆ ℕ, a vertex set S in a graph G is a (σ, ρ)-dominating set if for all v ∈ S, |N(v) ∩ S| ∈ σ, and for all v ∈ V(G) ⧵ S, |N(v) ∩ S| ∈ ρ. The Min/Max (σ,ρ)-Dominating Set problems ask, given a graph G and ... -
On the parameterized complexity of deletion to H-free strong components
(Journal article; Peer reviewed, 2020)Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the H-SCC Deletion ... -
On the Satisfiability of Smooth Grid CSPs
(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 ...