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 ...

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 ...

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 ...

For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc ...

Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given ...

We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...

We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity.

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class ...

In the Steiner Tree problem, we are given as input a connected \(n\)-vertex graph with edge weights in \(\{1,2,\ldots,W\}\), and a set of \(k\) terminal vertices. Our task is to compute a minimum-weight tree that contains ...