Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
MC From Scratch's user avatar
-4 votes
1 answer
220 views

What is the computationally simplest way to universally index the set of simple graphs?

If given a simple, integer-labeled, but not necessarily connected, graph $G := (V,E)$ consisting of at least one vertex, i.e. $\lvert \rvert V \lvert \rvert \geq 1$, then is there a function to ...
Stuart LaForge's user avatar
1 vote
1 answer
82 views

The complexity on calculation of the Graev metric on the free Boolean group of a metric space

For a set $X$ by $B(X)$ we denote the family of all finite subsets of $X$ endowed with the operation $\oplus$ of symmetric difference. This operation turns $B(X)$ into a Boolean group, which can be ...
Taras Banakh's user avatar
  • 41.8k
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 ...
LeechLattice's user avatar
  • 9,501
1 vote
0 answers
29 views

Existence of Costas array with specified displacment vectors?

Costas array is a set of $n$ points lying on the square of a $n×n$ checkerboard, such that each row or column contains only one point, and that all of the $n(n − 1)/2$ displacement vectors between ...
Mohammad Al-Turkistany's user avatar
6 votes
1 answer
173 views

What is the minimum worst-case length of an element removal game?

A game is played as follows. There is a set $X = \{1, \ldots, n\}$. Player 1 is trying to find a "locally minimal subset" $M \subseteq X$ - that is, player 2 has said that $M$ is good, and also that ...
David R. MacIver's user avatar
44 votes
4 answers
2k views

A curious process with positive integers

Let $k > 1$ be an integer, and $A$ be a multiset initially containing all positive integers. We perform the following operation repeatedly: extract the $k$ smallest elements of $A$ and add their ...
Mikhail Tikhomirov's user avatar
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 $\...
Mikhail Tikhomirov's user avatar
1 vote
0 answers
78 views

Bipartite clustering is NP-hard?

Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...
Thomas Edison's user avatar
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, ...
Lviv Scottish Book's user avatar
29 votes
2 answers
1k views

Determining if a rational function has a subtraction-free expression

This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class. Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
Christian Gaetz's user avatar
0 votes
1 answer
140 views

Maximum partition of bipartite graph

Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\...
Thomas Edison's user avatar
0 votes
0 answers
149 views

Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$?

We got an argument that 3-coloring bounded degree graphs is subexponential with complexity $O(\exp{(\sqrt{n}\log^2{n})})$. The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$ and 3-...
joro's user avatar
  • 25.4k
2 votes
1 answer
339 views

Bit complexity of Barvinok's algorithm

I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension. What exactly is this arithmetic complexity? ...
Turbo's user avatar
  • 13.9k
0 votes
1 answer
245 views

Modification of the subset sum problem - "perfect coverage" of the set with good solutions

I have a problem. We have a set. $S = (a_1, a_2 ... a_k)$ and an integer $x$. We know that there is a sum of elements to $x$ in it. We also know that: if there is only one sum to $x$ then it must ...
Aurelio's user avatar
  • 133
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 ...
Hauke Reddmann's user avatar
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 ...
Iltl's user avatar
  • 213
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)...
Mikhail Tikhomirov's user avatar
7 votes
2 answers
324 views

Graph isomorphism problem for minimally strongly connected digraphs

A minimally strongly connected digraph (MSC) is strongly connected (SC), while removal of any arc destroys this. That is, between any two vertices a, b there exists a directed path from a to b, while ...
Hoda Abbasizanjani's user avatar
19 votes
1 answer
616 views

How hard is it to tell when a finite set tiles the integers?

Given a nonempty set $B$ of integers between 1 and $n$, we wish to determine whether or not $\mathbb{Z}$ can be tiled with translates of $B$ (that is, covered by disjoint translates of $B$). I know an ...
James Propp's user avatar
  • 19.7k
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). ...
Rebecca J. Stones's user avatar
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 ...
joro's user avatar
  • 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 ...
T. Amdeberhan's user avatar
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 ...
Kuifje's user avatar
  • 225
19 votes
2 answers
1k views

Explicit invariant of tensors nonvanishing on the diagonal

The group $SL_n \times SL_n \times SL_n$ acts naturally on the vector space $\mathbb C^n \otimes \mathbb C^n \otimes \mathbb C^n$ and has a rather large ring of polynomial invariants. The element $$\...
Will Sawin's user avatar
  • 148k
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 ...
Iltl's user avatar
  • 213
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$. ...
SorcererofDM's user avatar
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(...
Arthur Kexu-Wang's user avatar
3 votes
2 answers
362 views

Sparse graphs that are hard to color

I am interested in knowing if there are any types of graphs that are very sparse, perhaps consisting of just connections between paths and cycles, and for which $k$-coloring is $\mathsf{NP}$-hard for ...
Iltl's user avatar
  • 213
11 votes
3 answers
3k views

Do you know a faster algorithm to color planar graphs?

while studying the four color theorem, I implemented an algorithm (in Python and Sage) that can color planar graphs much faster than the implementations I found around on internet. The program can be ...
Mario Stefanutti's user avatar
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 ...
Vicent's user avatar
  • 153
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 ...
Mario Stefanutti's user avatar
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 ...
Włodzimierz Holsztyński's user avatar
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 ...
user avatar
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 ...
Turbo's user avatar
  • 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 ...
Aaron Chen's user avatar
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 |\...
Alexey Milovanov's user avatar
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 ...
Pavan Sangha's user avatar
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 ...
Pavan Sangha's user avatar
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 ...
Bryce Sandlund's user avatar
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 ...
Campello's user avatar
  • 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 ...
Matt Samuel's user avatar
  • 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 ...
Pavan Sangha's user avatar
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 ...
Pavan Sangha's user avatar
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 ...
Brendan McKay's user avatar
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 $...
fanqi's user avatar
  • 11
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_{...
Iltl's user avatar
  • 213
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, \...
user66081's user avatar
  • 171
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 ...
Mark Lewko's user avatar
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$. ...
Kuifje's user avatar
  • 225