SIAM Journal on Computing · 2015 · 91 citations · 52 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationComputational ComplexityGraph AlgorithmsGraph TheoryClique AlgorithmsCliquesComputational Complexity Of Graph AlgorithmsMonadic Second-order LogicNp-complete ProblemsNp-hardnessPolynomial Time ComplexityPolynomial-time Algorithms
We obtain an algorithmic metatheorem for the following optimization problem. Let $\varphi$ be a counting monadic second order logic (CMSO) formula and $t\geq 0$ be an integer. For a given graph $G=(V,E)$, the task is to maximize $|X|$ subject to the following: there is a set $ F\subseteq V$ such that $X\subseteq F $, the subgraph $G[F]$ induced by $F$ is of treewidth at most $t$, and the structure $(G[F],X)$ models $\varphi$, i.e., $(G[F],X)\models\varphi$. We give an algorithm solving this optimization problem on any $n$-vertex graph $G$ in time ${\cal O}(|\Pi_G| \cdot n^{t+4}\cdot f(t,\varphi))$, where $\Pi_G$ is the set of all potential maximal cliques in $G$ and $f$ is a function of $t$ and $\varphi$ only. Pipelined with the known bounds on the number of potential maximal cliques in different graph classes, there are a plethora of algorithmic consequences extending and subsuming many known results on polynomial-time algorithms for graph classes. We also show that all potential maximal cliques of $G$ can be enumerated in time ${\cal O}(1.7347^n)$. This implies the existence of an exact exponential algorithm of running time ${\cal O}(1.7347^n)$ for many NP-hard problems related to finding maximum induced subgraphs with different properties.
52
A Computing Procedure for Quantification Theory
Martin Davis, Hilary Putnam · Journal of the ACM · 1960 · 2.6K citations · Full text
Easy problems for tree-decomposable graphs
Stefan Arnborg, Jens Lagergren, Detlef Seese · Journal of Algorithms · 1991 · 874 citations