Browsing Department of Informatics by Journals "SIAM Journal on Discrete Mathematics"
Now showing items 1-9 of 9
-
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 ... -
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 ... -
Kernelization of Graph Hamiltonicity: Proper H-Graphs
(Journal article; Peer reviewed, 2021)We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization ... -
Kernelization of Whitney Switches
(Journal article; Peer reviewed, 2021)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 ... -
More Applications of the d-Neighbor Equivalence: Acyclicity and Connectivity Constraints
(Journal article; Peer reviewed, 2021)In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced ... -
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 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 ... -
Path contraction faster than $2^n$
(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 ... -
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 ...