• Parameterized complexity classification of deletion to list matrix-partition for low-order matrices 

      Agrawal, Akanksha; Kolay, Sudeshna; Madathil, Jayakrishnan; Saurabh, Saket (Journal article; Peer reviewed, 2019)
      Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G) - > 2^{[l]} (where [l] = {1,2,...,l}), a list M-partition of G with respect to L is a partition of V(G) into l parts, ...
    • Parameterized complexity of conflict-free matchings and paths 

      Agrawal, Akanksha; Jain, Pallavi; Kanesh, Lawqueen; Saurabh, Saket (Journal article; Peer reviewed, 2019)
      An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) ...
    • Parameterized Complexity of Directed Spanner Problems 

      Fomin, Fedor; Golovach, Petr; Lochet, William; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2020)
      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 ...
    • Parameterized Complexity of Directed Spanner Problems 

      Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2021)
      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 ...
    • Parameterized complexity of Eulerian deletion problems 

      Cygan, Marek; Pilipczuk, Marcin; Marx, Dániel; Pilipczuk, Michal Pawel; Schlotter, Ildikó (Peer reviewed; Journal article, 2014-01)
      We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity ...
    • Parameterized Complexity of Feature Selection for Categorical Data Clustering 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2021)
      We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, ...
    • The Parameterized Complexity of Guarding Almost Convex Polygons 

      Agrawal, Akanksha; Knudsen, Kristine Vitting Klinkby; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)
      The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide ...
    • Parameterized complexity of PCA 

      Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2020)
      We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity.
    • Parameterized complexity of secluded connectivity problems 

      Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S (Peer reviewed; Journal article, 2015)
      The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of ...
    • Parameterized complexity of the spanning tree congestion problem 

      Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr; Otachi, Yota; van Leeuwen, Erik Jan (Peer reviewed; Journal article, 2012-09)
      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 ...
    • Parameterized Graph Modification Algorithms 

      Drange, Pål Grønås (Doctoral thesis, 2015-12-10)
      Graph modification problems form an important class of algorithmic problems in computer science. In this thesis, we study edge modification problems towards classes related to chordal graphs, with the main focus on trivially ...
    • Parameterized k-Clustering: Tractability Island 

      Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Peer reviewed; Journal article, 2019)
      In k-Clustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} ...
    • Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree 

      Fomin, Fedor; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (Peer reviewed; Journal article, 2019)
      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 ...
    • Parameterized streaming algorithms for min-ones d-SAT 

      Agrawal, Akanksha; Bonnet, Édouard; Curticapean, Radu; Miltzow, Tillmann; Saurabh, Saket; Biswas, Arindam; Brettell, Nick; Marx, Dániel; Raman, Venkatesh (Journal article; Peer reviewed, 2019)
      In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has ...
    • Parsing in a Broad Sense 

      Zaytsev, Vadim; Bagge, Anya Helene (Lecture Notes in Computer Science: 8767, Chapter; Peer reviewed, 2014)
      Having multiple representations of the same instance is common in software language engineering: models can be visualised as graphs, edited as text, serialised as XML. When mappings between such representations are considered, ...
    • Partially APN functions with APN-like polynomial representations 

      Budaghyan, Lilya; Kaleyski, Nikolay Stoyanov; Riera, Constanza Susana; Stănică, Pantelimon (Journal article; Peer reviewed, 2020)
      In this paper we investigate several families of monomial functions with APN-like exponents that are not APN, but are partially 0-APN for infinitely many extensions of the binary field F2. We also investigate the differential ...
    • Partitioning a graph into degenerate subgraphs 

      Abu-Khzam, Faisal; Feghali, Carl; Heggernes, Pinar (Journal article; Peer reviewed, 2020-01)
      Let G = (V, E) be a connected graph with maximum degree k ≥ 3 distinct from Kk+1. Given integers s ≥ 2 and p1, . . . , ps ≥ 0, G is said to be (p1, . . . , ps)-partitionable if there exists a partition of V into sets ...
    • Partitioning H-Free Graphs of Bounded Diameter 

      Brause, Christoph; Golovach, Petr; Martin, Barnaby; Paulusma, Daniël; Smith, Siani (Journal article; Peer reviewed, 2021)
      A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, ...
    • Passive Cryptanalysis of the UnConditionally Secure Authentication Protocol for RFID Systems 

      Abyaneh, Mohammad Reza Sohizadeh (Journal article, 2011)
      Recently, Alomair et al. proposed the first Un- Conditionally Secure mutual authentication protocol for lowcost RFID systems(UCS-RFID). The security of the UCSRFID relies on five dynamic secret keys which are updated at ...
    • Path contraction faster than $2^n$ 

      Agrawal, Akanksha; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Tale, Prafullkumar (Journal article; Peer reviewed, 2020)
      A graph $G$ is contractible to a graph $H$ if there is a set $X \subseteq E(G)$, such that $G/X$ is isomorphic to $H$. Here, $G/X$ is the graph obtained from $G$ by contracting all the edges in $X$. For a family of graphs ...