All Questions
Tagged with co.combinatorics computational-complexity
216 questions
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). ...
- 63.9k
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
2
votes
1
answer
240
views
valuation from $\mathbb{Z}^n$ into $\mathbb{Z}$. Easy way?
Let $\mathcal{F}:=\{f_a\}_{a\in\mathbb{Z}}$ be a set of symbols indexed by the integers and satisfying the rules:
$$f_a=f_{-a} \qquad \text{and} \qquad f_af_b=f_{a+b}+f_{a-b}.$$
Define a linear ...
- 43.2k
1
vote
1
answer
206
views
Show $0-1$ Knapsack is polynomially reducible to this problem
I have already posted this question here but have not received an answer so I am cross-posting with hope to reach a larger amount of mathematicians:
Let $T=\{1,\cdots,n\}$ and consider the ...
CommunityBot
- 1
5
votes
2
answers
413
views
An interesting variant on the maximum independent set problem.
Suppose i have a graph $G=(V,E)$ with $|V|=n$. Furthermore suppose i give you a maximum independent set $\mathcal{I}$ in $G$. Now suppose i obtain a new graph $G'$ from $G$ by removing a single vertex ...
CommunityBot
- 1
6
votes
2
answers
518
views
A minimum set hitting every base of a matroid
We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid. Is the problem studied before? Is it in P? For example, in ...
CommunityBot
- 1
3
votes
1
answer
158
views
Matroids of hypercubes
Let $M_k$ be the (oriented) matroid of the $2^k$ points $B_k = \{-1, 1\}^k$ in $\mathbb R^k$. In other words, the (oriented) circuits of $M_k$ are the minimal (signed) linear dependences among $B_k$.
...
- 984
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(...
- 17.6k
3
votes
1
answer
497
views
Which is the most time efficient algorithm for having a Tait Coloring (edge-3-coloring) of planar cubic graphs?
Crossposted from: https://math.stackexchange.com/questions/1964486/which-is-the-most-time-efficient-algorithm-for-having-a-tait-coloring-edge
I wasn't able to find an efficient algorithm nor an ...
CommunityBot
- 1
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 |\...
CommunityBot
- 1
1
vote
0
answers
1k
views
Number of different combinations in a 0-1 knapsack problem with integer weights [closed]
My question is actually very similar to this other one: Given a vector of positive integers, count the number of combinations which have a sum that produces a different value. But, since this previous ...
CommunityBot
- 1
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 ...
- 32.5k
1
vote
1
answer
357
views
Analysis of a partition algorithm
EDIT:
I realized that if $J$ is not a solution so is $J^c$. I updated the algorithm because of this.
Given some positive integers $x_1,\cdots, x_n$.
The following algorithm is for solving the ...
CommunityBot
- 1
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
11
votes
1
answer
950
views
Computational complexity of computing simplicial homology
Is there any literature regarding the fastest known algorithm to compute the homology groups of a simplicial complex (on n vertices)? What about computing the fundamental group? The context is to tell ...
- 7,875
1
vote
0
answers
139
views
bounded degree graph colouring.
I was wondering if anyone could provide references on the following:
Is determining the chromatic number of a bounded degree graph APX-complete?
2.I've seen the result that states it is NP-hard to ...
- 903
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
19
votes
3
answers
2k
views
A generalization of the triangle counting problem for simple weighted graphs
One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in sub-...
CommunityBot
- 1
12
votes
2
answers
292
views
Permutation search problems with no known $o(n!)$ algorithms
I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
- 15.8k
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
1
vote
1
answer
332
views
Graph colouring for bounded degree graphs
I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,
For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is ...
- 25.4k
2
votes
1
answer
93
views
Directed edge-colouring
I'm interested to know whether the following problem is NP-complete or if there is an algorithm to solve it.
Suppose we are given a directed graph $G=(V,E^{\rightarrow})$ and we want to colour the ...
- 109k
1
vote
0
answers
28
views
The complexity of Max-K interval selection
I came up with the following problem, but do not know how to analyze it.
Let $S$ be an ordered set of integers with size $n$ (i.e., $S=\{1,2,...,n\}$). An interval $INV(a,b)$ covers the elements in $...
- 19.6k
9
votes
1
answer
326
views
Factoring a multiset into a product of two multisets
Given a multiset $S$ of $mn$ numbers, how hard is to find multisets $A$ and $B$, of $m$ and $n$ numbers respectively, such that
$$ S = \{ xy \mid x\in A, y\in B \}~~~~\text{(multiset sense)}, $$
or ...
CommunityBot
- 1
1
vote
0
answers
34
views
Some confusion regarding the definition of NPO reduction
I've seen the following definition in a paper on approximation preserving reductions.
Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} \pi_{...
- 213
0
votes
0
answers
555
views
VC dimension and boolean hypercube subgraphs
Are there any well studied graph theoretic properties that are common to all subgraphs of the boolean hypercubes that have a given VC dimension d.
CommunityBot
- 1
4
votes
1
answer
140
views
Complexity of this minimization
For integer $N$ consider the mapping $$f : (0,1)^N \to \mathbb{R}, \quad x \mapsto \min_{b \in \{0,1\}^N} \left\{ x^b + x^{1-b} \right\},$$
where $x^b = x_1^{b_1} \cdots x_N^{b_N}$ and $1-b = (1-b_1, \...
- 1,927
6
votes
2
answers
2k
views
How can I prove that these two graph coloring problems are polynomial time equivalent?
Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$.
...
- 1,602
1
vote
1
answer
100
views
Is it known whether Minimum Cost Multicut is APX-hard?
My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$,
$$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \...
- 19.6k
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
7
votes
1
answer
304
views
"Separated" version of Sauer's lemma on VC classes
Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:
Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...
- 2,207
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 ...
CommunityBot
- 1
3
votes
1
answer
215
views
Construction of planar embedding
I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...
- 32.1k
18
votes
2
answers
2k
views
Can Schwartz-Zippel be formulated for commutative rings instead of fields?
The polynomials which occur in the Schwartz-Zippel lemma could be defined for any commutative ring, yet the lemma is restricted to fields. This makes it inapplicable for $(1+x^n)=1+x^n(\operatorname{...
CommunityBot
- 1
1
vote
2
answers
375
views
When is a power of an indeterminate in an ideal with 2 generators?
If I have an ideal ${\frak a} \colon= (f(X,S), g(X,S))$ of height $2$ in ${\Bbb C}[X, S]$, is it easy to know what power of $S$ is contained in $\frak a$? For example, what is the minimal number $m$? ...
- 1,961
8
votes
2
answers
3k
views
How to determine if there exists a non-zero vector in the kernel
If you are given a $0$-$1$ circulant matrix with $n$ rows and $n$ columns, is there an efficient way of determining if there exists a non-zero $\{-1,0,1\}$-vector in its kernel?
Could this problem ...
- 3,377
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 ...
CommunityBot
- 1
11
votes
2
answers
1k
views
An algorithm to find non-trivial linear dependencies
This question is inspired by another MO question about special stratifications of equivariant Grassmannians, that turned out to be a problem of computing non-trivial circuits in a vector matroid. To ...
CommunityBot
- 1
1
vote
1
answer
181
views
A particular argument in the review on expanders by Hoory-Linial-Wigderson
I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/
Can someone explain what is the argument there which seems to conclude ...
- 3,911
5
votes
1
answer
523
views
Finding sparsest solution of a linear system
I want to find the solution with most zero-components for the following problem:
$Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...
- 194
6
votes
3
answers
475
views
Complexity of high-order differentiation
Let $g(x) = \exp(f(x))$. Assuming numerical (or symbolic) values of $f(x), f'(x), f''(x), \ldots, f^{(n)}(x)$ are known, is there a way to compute $g'(x), g''(x), \ldots g^{(n)}(x)$ (or even the ...
- 2,235
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
140
views
Number of degree $k$ functions [closed]
Given a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, there is a real multivariate multilinear polynomial that is associated with in through interpolation.
Example: $AND(x_1,x_2,\dots,x_{n-1},x_n)...
- 13.9k
1
vote
0
answers
128
views
Reducing enumeration of reduced words in general Coxeter groups to another #P-complete problem
There is a polynomial time algorithm that takes as inputs a Coxeter system $(W,S)$ with $S$ finite (but with $W$ not necessarily finite), say encoded as a Coxeter matrix, as well as two reduced words ...
- 2,168
1
vote
1
answer
321
views
Cycles of Permutation Related to Rectangular Matrix Transposition
let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$
Question:
How can the first element ...
- 13.2k
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
1
answer
320
views
NP hard problems on UD graphs
I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard.
http://ac.els-cdn....
- 940
35
votes
1
answer
2k
views
How hard is reconstructing a permutation from its differences sequence?
My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
CommunityBot
- 1
15
votes
2
answers
512
views
Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?
Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by $\pi.(\sigma_1,\...
CommunityBot
- 1