|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Finding small separators in linear time via treewidth reduction | | Dániel Marx
; Barry O'Sullivan
; Igor Razgon
; | | Date: |
21 Oct 2011 | | Abstract: | We present a method for reducing the treewidth of a graph while preserving
all of its minimal $s-t$ separators up to a certain fixed size $k$. This
technique allows us to solve $s-t$ Cut and Multicut problems with various
additional restrictions (e.g., the vertices being removed from the graph form
an independent set or induce a connected graph) in linear time for every fixed
number $k$ of removed vertices.
Our results have applications for problems that are not directly defined by
separators, but the known solution methods depend on some variant of
separation. for example, we can solve similarly restricted generalizations of
Bipartization (delete at most $k$ vertices from $G$ to make it bipartite) in
almost linear time for every fixed number $k$ of removed vertices. These
results answer a number of open questions in the area of parameterized
complexity. Furthermore, our technique turns out to be relevant for $(H,C,K)$-
and $(H,C,le K)$-coloring problems as well, which are cardinality constrained
variants of the classical $H$-coloring problem. We make progress in the
classification of the parameterized complexity of these problems by identifying
new cases that can be solved in almost linear time for every fixed cardinality
bound. | | Source: | arXiv, 1110.4765 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER