Now showing items 1-20 of 28

• #### An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL ﻿

(Journal article; Peer reviewed, 2020)
In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge ...
• #### Approximating Acyclicity Parameters of Sparse Hypergraphs ﻿

(Conference object; Peer reviewed; Journal article, 2009)
The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized ...
• #### Clustering to Given Connectivities ﻿

(Peer reviewed; Journal article, 2019)
We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In Clustering to Given Connectivities, we are given an n-vertex graph G, an integer k, and ...
• #### Connecting Vertices by Independent Trees ﻿

(Conference object, 2014)
We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and ...
• #### Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals ﻿

(Peer reviewed; Journal article, 2019)
Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, an r-rank perturbed graphic matroid M is a binary matroid that can be represented ...
• #### Cyclability in Graph Classes ﻿

(Peer reviewed; Journal article, 2019)
A subset T subseteq V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is k-cyclable if every subset of vertices of G of size at ...
• #### Diverse Pairs of Matchings ﻿

(Journal article; Peer reviewed, 2020)
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse ...
• #### Editing to Eulerian Graphs ﻿

(Conference object, 2014)
We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and ...
• #### Enumerating minimal connected dominating sets in graphs of bounded chordality ﻿

(Conference object; Peer reviewed; Journal article, 2015)
Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration ...
• #### Going Far from Degeneracy ﻿

(Journal article; Peer reviewed, 2020)
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ös and Gallai from 1959, every graph of degeneracy $d>1$ contains a cycle of length at ...
• #### 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 ...
• #### Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable ﻿

(Journal article; Peer reviewed, 2020)
For a finite collection of graphs F, the F-TM-Deletion problem has as input an n-vertex graph G and an integer k and asks whether there exists a set S ⊆ V(G) with |S| ≤ k such that G \ S does not contain any of the graphs ...
• #### 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 ...
• #### 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 ...
• #### 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 ...
• #### 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 Tractability of Optimization Problems on H-Graphs ﻿

(Journal article; Peer reviewed, 2020)
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 Multiplicative Guarantee ﻿

(Journal article; Peer reviewed, 2020)
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 ...
• #### Parameterized Complexity of Directed Spanner Problems ﻿

(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 PCA ﻿

(Journal article; Peer reviewed, 2020)
We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity.