Now showing items 1-20 of 22

• #### B-chromatic number: Beyond NP-hardness ﻿

(Conference object; Peer reviewed; Journal article, 2015)
The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ...
• #### Balanced judicious bipartition is fixed-parameter tractable ﻿

(Journal article; Peer reviewed, 2019)
The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of ...
• #### Connecting the Dots (with Minimum Crossings) ﻿

(Journal article; Peer reviewed, 2019)
We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ...
• #### 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 ...
• #### Decomposition of map graphs with applications ﻿

(Peer reviewed; Journal article, 2019)
• #### Exact and approximate digraph bandwidth ﻿

(Journal article; Peer reviewed, 2019)
In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of ...
• #### Finding even subgraphs even faster ﻿

(Conference object; Peer reviewed; Journal article, 2015)
Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k ...
• #### 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 ...
• #### Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves ﻿

(Conference object; 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 ...
• #### On cutwidth parameterized by vertex cover ﻿

(Peer reviewed; Journal article, 2014-04)
We study the CUTWIDTH problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two ...
• #### Packing arc-disjoint cycles in tournaments ﻿

(Journal article; Peer reviewed, 2019)
A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining ...
• #### Packing cycles faster than Erdos-Posa ﻿

(Journal article; Peer reviewed, 2019)
The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant attention ...
• #### Parameterized complexity classification of deletion to list matrix-partition for low-order matrices ﻿

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

(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 Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ﻿

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

(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 ...
• #### Path Contraction Faster Than 2n ﻿

(Peer reviewed; Journal article, 2019)
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 F, the F-Contraction ...
• #### Quick but odd growth of cacti ﻿

(Conference object; Peer reviewed; Journal article, 2015)
Let F be a family of graphs. Given an input graph G and a positive integer k, testing whether G has a k-sized subset of vertices S, such that G\S belongs to F, is a prototype vertex deletion problem. These type of problems ...
• #### Rank vertex cover as a natural problem for algebraic compression ﻿

(Journal article; Peer reviewed, 2019)
The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a long-standing, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and ...