Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth
140
0
0.0
(
0
)
Added by
Mugurel Ionut Andreica
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Mugurel Ionut Andreica
Ask ChatGPT about the research
No Arabic abstract
In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the networks performance and fault tolerance. The main technique considered in this paper is dynamic programming.
rate research
Read More
We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable in graphs of bounded treewidth. These schemes apply in all fractionally treewidth-fragile graph classes, a property that is true for many natural graph classes with sublinear separators. We also provide quasipolynomial-time approximation schemes for these problems in all classes with sublinear separators.
We give a constant factor approximation algorithm for the asymmetric traveling salesman problem when the support graph of the solution of the Held-Karp linear programming relaxation has bounded orientable genus.
Large graphs abound in machine learning, data mining, and several related areas. A useful step towards analyzing such graphs is that of obtaining certain summary statistics - e.g., or the expected length of a shortest path between two nodes, or the expected weight of a minimum spanning tree of the graph, etc. These statistics provide insight into the structure of a graph, and they can help predict global properties of a graph. Motivated thus, we propose to study statistical properties of structured subgraphs (of a given graph), in particular, to estimate the expected objective function value of a combinatorial optimization problem over these subgraphs. The general task is very difficult, if not unsolvable; so for concreteness we describe a more specific statistical estimation problem based on spanning trees. We hope that our position paper encourages others to also study other types of graphical structures for which one can prove nontrivial statistical estimates.
We investigate the performance of a variant of Axelrods model for dissemination of culture - the Adaptive Culture Heuristic (ACH) - on solving an NP-Complete optimization problem, namely, the classification of binary input patterns of size $F$ by a Boolean Binary Perceptron. In this heuristic, $N$ agents, characterized by binary strings of length $F$ which represent possible solutions to the optimization problem, are fixed at the sites of a square lattice and interact with their nearest neighbors only. The interactions are such that the agents strings (or cultures) become more similar to the low-cost strings of their neighbors resulting in the dissemination of these strings across the lattice. Eventually the dynamics freezes into a homogeneous absorbing configuration in which all agents exhibit identical solutions to the optimization problem. We find through extensive simulations that the probability of finding the optimal solution is a function of the reduced variable $F/N^{1/4}$ so that the number of agents must increase with the fourth power of the problem size, $N propto F^ 4$, to guarantee a fixed probability of success. In this case, we find that the relaxation time to reach an absorbing configuration scales with $F^ 6$ which can be interpreted as the overall computational cost of the ACH to find an optimal set of weights for a Boolean Binary Perceptron, given a fixed probability of success.
It has long been known that Feedback Vertex Set can be solved in time $2^{mathcal{O}(wlog w)}n^{mathcal{O}(1)}$ on $n$-vertex graphs of treewidth $w$, but it was only recently that this running time was improved to $2^{mathcal{O}(w)}n^{mathcal{O}(1)}$, that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class $mathcal{P}$ of graphs, the Bounded $mathcal{P}$-Block Vertex Deletion problem asks, given a graph~$G$ on $n$ vertices and positive integers~$k$ and~$d$, whether $G$ contains a set~$S$ of at most $k$ vertices such that each block of $G-S$ has at most $d$ vertices and is in $mathcal{P}$. Assuming that $mathcal{P}$ is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of $d$: if $mathcal{P}$ consists only of chordal graphs, then the problem can be solved in time $2^{mathcal{O}(wd^2)} n^{mathcal{O}(1)}$, and if $mathcal{P}$ contains a graph with an induced cycle of length $ellge 4$, then the problem is not solvable in time $2^{o(wlog w)} n^{mathcal{O}(1)}$ even for fixed $d=ell$, unless the ETH fails. We also study a similar problem, called Bounded $mathcal{P}$-Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if $d$ is part of the input and $mathcal{P}$ contains all chordal graphs, then it cannot be solved in time $f(w)n^{o(w)}$ for some function $f$, unless the ETH fails.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
