All Questions
Tagged with co.combinatorics computational-complexity
77 questions with no upvoted or accepted answers
21
votes
0
answers
441
views
Straight-line drawing of regular polyhedra
Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).
For example, ...
- 4,535
17
votes
0
answers
449
views
Splay trees and Thompson's group $F$
( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...
- 992
13
votes
0
answers
713
views
Regular languages of matrices and their generating functions
My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
- 3,897
10
votes
0
answers
454
views
Fast method to verify if a point belongs to a given convex $d$-polytope
We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...
- 1,677
9
votes
0
answers
2k
views
Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere
Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
- 311
9
votes
0
answers
2k
views
Weighted Hamming distance
Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is combinatorics but similar things come up sometimes in theoretical computer science, ...
- 24.8k
8
votes
0
answers
237
views
Size of 3-SAT assignments
Let $F(N,M)$ be the set of 3-SAT formula with $N$ variables and $M$ clauses. For a given formula $f\in F(N,M)$, we can ask for the set $s_f$ of truth assignments that satisfy $f$. (If $f$ is ...
- 3,979
8
votes
0
answers
88
views
Is recognizing if a Latin square is isotopic to its transpose more efficient than computing its symmetry group?
Ihrig and Ihrig (2007) described a mathematical method for determining if a Latin square is isotopic to its transpose (where isotopic Latin squares vary by permuting the rows, columns and symbols). ...
- 1,327
8
votes
0
answers
288
views
Recognizing sequences sortable by transpositions?
While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from ...
- 2,993
7
votes
0
answers
203
views
Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs
Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a ...
- 965
7
votes
0
answers
93
views
Combinatorial region-halfplane incidence structures
I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate.
Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\...
- 5,590
7
votes
0
answers
342
views
Multidimensional hook length formula
A well-known hook length formula states that the number of ways to arrange the elements of $[n]$ in a Young tableau with $n$ cells so that all columns and rows are increasing is $\frac{n!}{\prod_c h(c)...
- 5,590
6
votes
0
answers
208
views
Is there a decomposition strengthening of the Sauer-Shelah Lemma?
Let $S \subset \{-1,1\}^n$. For a subset $A \subset [n]$ let $P_A$ denote the coordinate projection operator on S; in other words let $P_A(S)$ be the coordinate projection of $S$ onto the coordinates ...
- 13k
6
votes
0
answers
154
views
Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph
According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...
- 25.4k
6
votes
0
answers
346
views
Enumerating (generalized) de Bruijn tori
Given a cyclic word $w$ of length $N$ over a $q$-ary alphabet and $k \in \mathbb{Z}_+$, consider the directed multigraph $G_k(w) = (V,E)$ with $V \subset$ {$1,\dots,q$}$^k$ given by the $k$-lets (i.e.,...
- 15.4k
5
votes
0
answers
301
views
The expressiveness of functions computable on trees
Motivation:
Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...
- 3,871
5
votes
0
answers
145
views
Complexity of $\mathbb{Z}^n$ tilings
Let $\mathcal{T} \subset \mathbb{Z}^n$ be a finite set. Let $\Lambda \subset \mathbb{Z}^n$ be a full rank lattice.
We say that $\mathcal{T}$ is a $\Lambda$-tile for $\mathbb{Z}^n$ if the following ...
- 800
5
votes
0
answers
222
views
Littlewood-Richardson rule for the complete flag variety: GapP complete?
The cohomology ring of a complete flag variety $X$ has a basis of Schubert classes $S_u$ for permutations $u$. Define the Littlewood-Richardson coefficient $c_{uv}^w$ for permutations $u,v,w$ to be ...
- 2,168
4
votes
0
answers
155
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 2,993
4
votes
0
answers
182
views
Determine the minimal elements of a Dynkin system generated by a finite set of finite sets
(This is a refined version of https://cs.stackexchange.com/q/144371)
Let $\Omega$ be a finite set. A Dynkin system on $\Omega$ is a subset of the power set of $\Omega$ containing $\Omega$, which is ...
- 5,822
4
votes
0
answers
84
views
Complexity of counting colorings of co-bipartite graphs?
A graph is co-bipartite if it is the complement of bipartite graph.
What is the complexity of counting colorings of co-bipartite graphs?
Unlike split graphs, the chromatic polynomial isn't of ...
- 25.4k
4
votes
0
answers
155
views
Effective "almost enumeration" of monotone boolean functions
Denote by $\mathcal{M}(n)$ the set of all monotone functions $\{0,1\}^n \to \{0,1\}$.
Can $\mathcal{M}(n)$ be represented as $\mathcal{M}(n) = \{ f(t) | t\in \{0,1\}^k \}$ such that:
1) $k = \log |\...
- 2,576
4
votes
0
answers
175
views
What is known about the complexity of this covering problem?
Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
- 2,966
4
votes
0
answers
73
views
Is the $d$-dimensional Arrangement of Trees still $NP$-hard?
The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
- 41
4
votes
0
answers
242
views
Domination in Nice Lattices
Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...
- 1,288
3
votes
0
answers
130
views
Is counting Latin squares #P-complete?
I feel like I should know the answer to this. I did some Googling and didn't easily find the answer...
Question: Is counting Latin squares #P-complete?
Obviously the corresponding decision problem &...
- 1,327
3
votes
0
answers
132
views
Can equality of chromatic symmetric functions of two trees be checked in polynomial time?
Stanley defined chromatic symmetric functions (CSF) in 1995 (Advances in Math) where he conjectured that trees can be distinguished by their CSF. However, tree isomorphism is decidable in P (...
- 31
3
votes
0
answers
98
views
Is the Graph Isomorphism problem in βP class?
βP is the limited nondeterminism NP, cf. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap
Last year Laslo Babai proved that the GI problem can be solved in (deterministic) time
$\exp(\log^c(...
- 193
3
votes
0
answers
230
views
On weight enumerators of codes
Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of ...
- 13.9k
3
votes
0
answers
181
views
Hypergraph edge colouring
I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...
- 903
2
votes
0
answers
81
views
Degeneracy and the "Linear Degeneracy Testing" problem
The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
- 153
2
votes
0
answers
245
views
Pancake sorting problem – Is computing f(n) NP-hard?
The so-called Pancake flipping problem first discussed by Jacob E. Goodman here yields two entangled problems:
MIN-SBPR (Sorting By Prefix Reversals) - Given a permutation, find the smallest sequence ...
- 51
2
votes
0
answers
91
views
Blind construction of planar graph with additive spanning tree count
Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count ...
- 13.9k
2
votes
0
answers
64
views
Polynomial-time algorithm for uniformly sampling the $n$-slice of a context-free language
Let $L\subset \Sigma^*$ be a context-free language. The $n$-slice is the intersection $L\cap \Sigma^n$ for a non-negative integer $n$.
Is there a polynomial-time algorithm for uniformly sampling from ...
- 21
2
votes
0
answers
70
views
Isomorphism preserving transformation graph to graph of logarithmic boolean width and bounded degeneracy
The paper On graph classes with logarithmic boolean-width
claims that some graph problems are fixed parameter tractable with parameter
the boolean width.
In particular, boolean-width of the complement ...
- 25.4k
2
votes
0
answers
81
views
Number of solutions to linear diophantine equations, with natural coefficients in a box
Let c, k, d $ \in \mathbb{N} $, let a, x $ \in \mathbb{N}^k $ suppose for all i $ \leq $ k, $ x_i \leq d $, $ a_i \in \mathcal{O}(d2^i) $ and $ \sum{a_ix_i} = c $ my question is for the value of c ...
2
votes
0
answers
62
views
A combinatorial question about encoding the subsets of logarithmic-bounded cardinality
Let $k \in \mathbb N - \{0\}$ and $f(n) = \binom n 0 + \binom n 1 + \dotsc + \binom n {\log^k n}$.
Our question is:
$f(n) = o(2^{\log^{k+1} \ (n)})$ or $f(n) = \Theta(2^{\log^{k+1} \ (n)})$, which ...
- 193
2
votes
0
answers
77
views
Confirming existence in polynomial time while solution finding is NP-complete
Assume P≠NP.
Say there's an NP-complete decision problem:
Does $P$ have a $Q$ ?
And we have a proposition $F$ computable in polynomial time, where $F(P)$ implies the existence of a solution in ...
- 9,501
2
votes
0
answers
113
views
How many bits/questions does it take to identify the most frequent number in an array?
Note that "most frequent" here means "any of the most frequent, don't care which".
Example $n=3$. Consider the Bell partitions
aaa
aab
aba
baa
abc
which subsume all possibilities of a 3 element array ...
- 4,829
2
votes
0
answers
254
views
maximum independent set in d-regular graphs
Does anyone know whether the maximum independent set problem is NP-hard in triangle free d-regular graphs and if it's NP-hard for all d larger than some threshold t? Can anyone provide a reference ...
- 213
2
votes
0
answers
146
views
Is pos(n) an algorithmic counter?
Let $\ \mathbf N = \{1\ 2\ \ldots\}\ $ be the set of natural numbers. Let $\ f : \mathbf N\rightarrow\mathbf N\ $ be an arbitrary function, and $\ \forall_{n\in\mathbf N}\, F(n)\ :=\ \max_{k = 1\ldots ...
- 7,500
2
votes
0
answers
151
views
How hard is recognizing a permutation that is a square for the shift product?
This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...
- 2,993
2
votes
0
answers
318
views
Determining strong base-orderability of a matroid
A matroid is said to be strongly base-orderable when for any two bases $B_1,B_2$ there exists a bijection $f:B_1 \mapsto B_2$ such that for any $X\subseteq B_1$ set $B_1 - X+ f(X)$ is also a base.
...
- 341
2
votes
0
answers
350
views
NP hard problems on geometric graphs
I have posted this question before but i don't feel i expressed my confusion clearly enough. So i would like to try and explain again. This is a proof of the minimum vertex cover for unit disk graphs ...
- 903
2
votes
0
answers
90
views
Computing basis of a lower set given basis of complementary upper set
In a poset $P$, $U\subseteq P$ is an upper set when for all $x\in U$, we have $y\ge x$ implies $y\in U$. Any subset of $P$ generates an upper set, and the basis of an upper set $U$ is the smallest ...
- 455
2
votes
0
answers
131
views
characterization of all periodic tiling of a simple set of Wang Tile
Consider a set of Wang Tile such that all the edges are either 1 or 0.... there are 16 elements in such a set.
Now, I wish to characterize all the periodic tilings of this set (better if they are ...
- 867
2
votes
0
answers
642
views
Hamiltonian paths in subgraphs of rectangular lattice graphs
Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of rectangular ...
2
votes
0
answers
289
views
Finding globally minimal row subsets of an integer matrix which generate the full row span
Given a $n\times m$ integer matrix $A$, we can consider its row span $span(A)$, that is, the minimal sublattice of $\mathbb{Z}^m$ containing all rows of $A$.
Given a subset of the rows of $A$ it is ...
- 5,654
1
vote
0
answers
92
views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question.
Is there a way to show within an ...
- 13.9k
1
vote
0
answers
101
views
On determinant and permanent of certain homotopy defined simple matrices
Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$
$$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$
hold ($per$ refers to permanent).
I. What ...
- 13.9k