Some observations on holographic algorithms
Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)
The author introduces a notion of \textit{diversity} for families of finite functions in terms of the number of different functions that can be obtained by fixing some variables. He then first shows how known reductions for many NP-complete problems yield characterizations in terms of this notion. He furthermore introduces a notion of \textit{elementary reduction to matchgrids}, generalizing the one of the author [``Accidental algorithms, in: Proceedings of the 47th annual IEEE symposium on foundations of computer science, FOCS'06. Los Alamitos, CA: IEEE Computer Society. 509--517 (2006)], specific to reductions from 3CNF, and shows that such a reductions also imposes constraints in terms of diversity. Finally, using the three-element basis \textbf{b3} from [the author, SIAM J. Comput. 37, No. 5, 1565--1594 (2008; Zbl 1152.05010)], the paper presents polynomial-time algorithms for problems for planar undirected graphs of degree three, namely, computing the parity of the number of solutions for feedback vertex sets, connected vertex covers, and vertex 3-colorings up to permutations of colors.
- Some observations on holographic algorithms
- scientific article; zbMATH DE number 3913673
- Planar 3DM is NP-complete
- The computational complexity of graph problems with succinct multigraph representation
- On unique graph 3-colorability and parsimonious reductions in the plane
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- scientific article; zbMATH DE number 4187829
- Comparing the Expressibility of Languages Formed Using NP-Complete Operators
- Base collapse of holographic algorithms
- Basis collapse for holographic algorithms over all domain sizes
- Computational complexity of counting problems on 3-regular planar graphs
- Computing and Combinatorics
- Expressiveness of matchgates.
- Holographic Algorithms
- scientific article; zbMATH DE number 3848625 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1443271 (Why is no real title available?)
- scientific article; zbMATH DE number 3257409 (Why is no real title available?)
- Matchgates revisited
- On Approximately Counting Colorings of Small Degree Graphs
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- On the theory of matchgate computations
- On unique graph 3-colorability and parsimonious reductions in the plane
- Planar Formulae and Their Uses
- Reducibility among combinatorial problems
- Some Results on Matchgates and Holographic Algorithms
- The complexity of computing the permanent
- The complexity of counting in sparse, regular, and planar graphs
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- The Complexity of Enumeration and Reliability Problems
- The Complexity of Planar Counting Problems
- The Rectilinear Steiner Tree Problem is NP-Complete
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Holographic algorithms: the power of dimensionality resolved
- FKT is not universal -- a planar holant dichotomy for symmetric constraints
- Holographic Algorithms
- Holographic algorithms: from art to science
- Some observations on holographic algorithms
- Some Results on Matchgates and Holographic Algorithms
- Automata, Languages and Programming
- Bipartite 3-regular counting problems with mixed signs
- Bipartite 3-regular counting problems with mixed signs
- Holographic algorithms on domains of general size
- On the fine-grained complexity of parity problems
This page was built for publication: Some observations on holographic algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1616615)
