A recent trend in parameterized algorithms is the application of polytope tools to fixed-
parameter tractable (FPT) algorithms eg, Cygan et al., FOCS 2011, 52nd Annual Symposium …

In this paper, we propose an algorithm that, given an undirected graph $ G $ of $ m $ edges
and an integer $ k $, computes a graph $ G'$ and an integer $ k'$ in $ O (k^ 4 m) $ time such …

A recent trend in the design of FPT algorithms is exploiting the half-integrality of LP
relaxations. In other words, starting with a half-integral optimal solution to an LP relaxation …

The matroid parity (or matroid matching) problem, introduced as a common generalization of
matching and matroid intersection problems, is so general that it requires an exponential …

We prove the existence of a computable function f∶ ℕ→ ℕ such that for every integer k and
every digraph D, either D contains a collection C of k directed cycles of even length such that …

A Γ-labeled graph is a directed graph G in which each edge is associated with an element of
a group Γ by a label function ψ: E (G)→ Γ. For a vertex subset A⊆ V (G), a path (in the …

Given an undirected graph $ G=(V, E) $ with a set of terminals $ T\subseteq V $ partitioned
into a family $\mathcal {S} $ of disjoint blocks, find the maximum number of vertex-disjoint …

The parity of the length of paths and cycles is a classical and well-studied topic in graph
theory and theoretical computer science. The parity constraints can be extended to label …

Mader's disjoint S-paths problem unifies two generalizations of bipartite matching:(a) non-
bipartite matching and (b) disjoint s–t paths. Lovász (1980, 1981) first proposed an efficient …

We study a constrained shortest path problem in group-labeled graphs with nonnegative
edge length, called the shortest non-zero path problem. Depending on the group in …