Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
On multiway cut parameterized above lower bounds
View through CrossRef
We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the
node multiway cut
problem is fixed-parameter tractable (FPT) in this setting. As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon.
Our results imply
O
*
(4
k
) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an
O
*
(2
k
) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.
Association for Computing Machinery (ACM)
Title: On multiway cut parameterized above lower bounds
Description:
We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the
node multiway cut
problem is fixed-parameter tractable (FPT) in this setting.
As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon.
Our results imply
O
*
(4
k
) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an
O
*
(2
k
) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.
Related Results
Parameterized Strings: Algorithms and Applications
Parameterized Strings: Algorithms and Applications
The parameterized string (p-string), a generalization of the traditional string, is composed of constant and parameter symbols. A parameterized match (p-match) exists between two p...
ANALYSIS OF FACTORS INFLUENCING ADHERENCE TO ANTIRETROVIRAL MEDICATION (ARV) IN HIV/AIDS PATIENTS BASED ON INFORMATION, MOTIVATION, BEHAVIORAL SKILLS AT CUT MEUTIA GENERAL HOSPITAL
ANALYSIS OF FACTORS INFLUENCING ADHERENCE TO ANTIRETROVIRAL MEDICATION (ARV) IN HIV/AIDS PATIENTS BASED ON INFORMATION, MOTIVATION, BEHAVIORAL SKILLS AT CUT MEUTIA GENERAL HOSPITAL
HIV (Human Immunodeficiency Virus), included in the Retroviridae family, is a virus that causes AIDS (Acquired Immunodeficiency Syndrome), a syndrome caused by a decrease in the bo...
Multilinear Mathematical Separation in Chromatography
Multilinear Mathematical Separation in Chromatography
Chromatography is a powerful and generally applicable method for the analytical separation and quantification of the chemical constituents in complex mixtures because chromatograph...
Exact and parameterized algorithms for choosability
Exact and parameterized algorithms for choosability
Abstract
In the Choosability problem (or list chromatic number problem), for a given graph G, we need to find the smallest k such that G admits a list coloring for any li...
Depth lower bounds in Stabbing Planes for combinatorial principles
Depth lower bounds in Stabbing Planes for combinatorial principles
Stabbing Planes (also known as Branch and Cut) is a proof system introduced
very recently which, informally speaking, extends the DPLL method by branching
on integer linear inequal...
Clique Cover and Graph Separation
Clique Cover and Graph Separation
The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this article, we show that, unless the ...
The habitability of Earth-like (exo)planets: modelling and limitations.
The habitability of Earth-like (exo)planets: modelling and limitations.
Quick take: We investigate the conditions behind exoplanetary habitability. We compare how different models (complex physics-based vs. parameterized evolution) estimate the climate...
Homotopies in Multiway (Nondeterministic) Rewriting Systems as n-Fold Categories
Homotopies in Multiway (Nondeterministic) Rewriting Systems as n-Fold Categories
We investigate algebraic and compositional properties of abstract multiway rewriting systems, which are archetypical structures underlying the formalism of the Wolfram model. We de...