Questions tagged [co.combinatorics]
Questions related to combinatorics and discrete mathematical structures
628
questions
8
votes
1answer
213 views
Does Horn SAT (Horn formula in CNF) have an integral polytope?
In some ways, my question is related to this: Is the matching polytope integral?
Matching and Horn-SAT are both polynomial time solvable.. So I wonder if there is a Horn polytope, similar to the ...
0
votes
0answers
21 views
Going from one base packing to another using basis exchanges
Suppose I have a matroid $M = (E, \mathcal{I})$. It is a known fact that given any two bases $X_0$ and $X_n$, we can transform $X_0$ into $X_n$ by repeatedly applying the basis exchange axiom. So ...
4
votes
2answers
223 views
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Preliminaries
We consider directed bipartite graphs of the form $G = (V,V',E)$, in which the nodes are partitioned into $V = \{1,\ldots,n\}$ and $V'=\{1',\ldots,n'\}$, with $|V|=|V'|=n$, and $E\...
1
vote
1answer
92 views
Partition the edges of a bipartite graph into perfect $b$-matchings
Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings.
I want to know whether a version of this extends to perfect $b$-matchings.
Suppose we have a bipartite graph $G =...
0
votes
1answer
114 views
Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?
Often, we can model combinatorial optimization problems with an Integer Program. Then there is an associated Linear Relaxation which drops the integrality constraints on the variables.
Let's say we ...
6
votes
1answer
278 views
Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries
My question concerns the NP-hardness of the following discrete optimization problem:
Given a matrix $A \in \{ \pm 1 \}^{m\times n}$,
$$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm ...
1
vote
1answer
80 views
Is there a regular bipartite graph where the minimum cuts are trivial?
My question is: Given integers $r$ and $k$, is there an $r$-regular bipartite graph $G = L \cup R$ with $|L| = |R| = k$, which is $r$-edge connected, and such that every minimum cut is trivial?
We can ...
2
votes
1answer
120 views
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
3
votes
1answer
149 views
TSP with "enemy" nodes
I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for.
The story/idea ...
3
votes
1answer
338 views
How hard is this combinatorial optimisation problem?
Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, ...
2
votes
1answer
71 views
Covering a binary relation as a union of rectangles
Given finite sets $X$ and $Y$ and a subset $R\subset X\times Y$, I want to express $R$ as a union $R=\bigcup_{i=1}^n X_i\times Y_i$ with $n$ as small as possible. Here, each $X_i\subset X$ and $Y_i\...
4
votes
1answer
175 views
Does such a bipartite graph exist?
In the course of my studies on graphs I sometimes use gadgets. I recently came upon a need for a certain bipartite graph with the following properties, and I am wondering if anyone knows if such a ...
0
votes
0answers
79 views
Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$
Crossposted at MathOverflow
A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$. $\mathbf{1}$ is ...
3
votes
0answers
85 views
Boltzmann sampling for containers/dependent polynomials?
I’d like to randomly sample from dependently-typed data structures.
Has anyone looked at extending Boltzmann sampling to containers or dependent polynomials?
0
votes
0answers
55 views
Prove that this linear relaxation has half-integral extreme points
Given a graph $G=(V,E)$, here is a Linear Relaxation of the edge cover polytope:
(1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$
(2) For each $e \in E$, $0 \leq x_e \leq 1.$
Here $\delta(S)$...
5
votes
0answers
151 views
Minimum spanning tree, but with an unusual objective function
This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem.
If we have a rooted tree $T = (V,E)$ with root $r$, I first label ...
3
votes
2answers
169 views
XOR Resilient Encoding
I am looking for an efficient encoding algorithm $E:\{0,1\}^n\to\{0,1\}^m$ such that given $E(x)\oplus E(y)$ for $x\neq y$, we can reconstruct $x$ and $y$.
One example of such an algorithm would be ...
0
votes
0answers
27 views
Unique naming/labeling of $40$-node strongly regular graphs
Brendan McKay's webpage lists all possible $40$-node strongly regular graphs. Is there a standard way to name them uniquely?
2
votes
1answer
34 views
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here.
Consider a ...
-2
votes
1answer
109 views
0
votes
0answers
40 views
are there approximation algorithms that use primal-dual with LP values and/or rounding?
Are there approximation algorithms that use primal-dual with LP values and/or rounding?
e.g. An algorithm that during any iteration first tries to see an extreme point to the LP has any value above a ...
7
votes
1answer
157 views
Inferring the Kolmogorov complexity of a string from its substrings' complexity
I know that the Kolmogorov complexity of a substring $v$ of an incompressible string $x$ has $C(v)\geq |v|-O(\log{|x|})$ , but I'm wondering if it is also possible to infer the complexity of a string ...
2
votes
1answer
88 views
"Parity testing set" for disjoint pairs of sets
I'd like a construction of the following description. Let $V$ be a set of $n$ elements. I'd like a collection $X$ of subsets of $V$ such that for any pair $(P,Q)$ of disjoint subsets of $V$, there ...
0
votes
0answers
92 views
How many maximal planar graphs are there?
We denote by a triangulation a (simple) maximal planar graph. How many triangulations on $n$ vertices are there? How many triangulations are there if we cannot distinguish the vertices, i.e. ...
0
votes
1answer
136 views
Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$
Let $G=(V,E)$ be a random $\Delta$-regular graph with $\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence ...
2
votes
0answers
98 views
$k$-XOR collision free families
Given parameters $n,k\in \mathbb N^+$, I'm interested in finding a set of binary vectors $V_{n,k}=\{v_1,\ldots,v_n\}$ of length that satisfies:
$\forall i: v_i\in\{0,1\}^{z_{n,k}}$.
The bitwise xor ...
2
votes
0answers
57 views
Damerau–Levenshtein distance with transposition of non-adjacent characters?
Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want ...
0
votes
0answers
34 views
Combinatorial object for a rational generating function
The is a well-established connection between generating functions and the specification of combinatorial objects via symbolic and/or analytic combinatorics.
A number of packages (e.g. SAGE) allow the ...
2
votes
1answer
135 views
Is this homework problem on T-joins wrong? [closed]
In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.
0
votes
0answers
76 views
Graph-based backjumping vs Conflict-based backjumping comparison in CSP
Graph-based backjumping vs Conflict-based backjumping in CSP
I have been studying techniques to find solutions in backtracking to model and solve a problem in c++ with this methods and I have the ...
1
vote
2answers
107 views
Where to find info on (polytime) approximability of various discrete optimization problems?
Where to find info on (polytime) approximability of various discrete optimization problems?
Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of ...
-4
votes
1answer
50 views
does within the "range a and b" include a and b?
I have not found the answer to this doubt of mine elsewhere, hence posting it here.
It may be a silly question but I just want to be sure :P
would be great if someone could help me out with this ...
1
vote
0answers
114 views
Quantum error correction and graph codes
I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
1
vote
1answer
86 views
Name of (and solution to) this generalization of linear assignment
I would like to know if the following problem is known and has any efficient solution.
Given an $n\times n$ score matrix $S$. Find the best $a$ elements, in terms of their sum of scores, such that no ...
2
votes
1answer
97 views
NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part
Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the ...
11
votes
3answers
554 views
Applications of sunflower lemma in theoretical computer science
In one lecture by Kewen Wu who is one of the authors of paper
Improved bounds for the sunflower lemma,
it is said that the sunflower lemma can be applied to many fields like
circuit lower bounds
...
2
votes
2answers
121 views
On the coloring number of small graphs with small cliques
Given a parameter $k$, and a graph $G$ with $O(k^2)$ vertices that has a maximum clique with $\le k$ vertices, I want to investigate the maximum number of colors $C(k)$ needed to properly color $G$, i....
0
votes
1answer
53 views
weights in low density codes
Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles ...
1
vote
1answer
78 views
Existence of graphs of every order related to Barnette’s conjecture
Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal ...
4
votes
1answer
206 views
Level $k$ bounds in Analysis of Boolean functions
In Ryan O'Donnell's book Analysis of Boolean functions, following Corollary 9.25 the following appears:
If $f\colon \{-1,1\}^n \to \{0,1\}$, and we have $\mathbb{E}[f] = \alpha$, then for any integer ...
3
votes
1answer
190 views
Dual to hypercontractive inequality
Recall the hypercontractive inequality:
Let $\rho = \sqrt{\frac{p-1}{q-1}}$, then $||T_\rho(f)||_q \leq ||f||_p$
In https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf it is stated that the ...
4
votes
1answer
252 views
How tight is the XOR lemma?
The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, ...
6
votes
1answer
290 views
Re-packing of integers into fixed-size bins
We are given a constant $B \geq 3$, a set of positive integers $I$ s.t. $\forall i \in I, i \leq B$ and $\sum_{i \in I} = N$,
and 2) a packing of these numbers into $N/B > 1$ bins of size $B$.
An ...
-1
votes
1answer
66 views
Chomsky-Schutzenberg Hierarchies explained for physicist (general) [closed]
I am classically trained in physics, however I have been interested in the use of information theory in studying some classical systems.
As someone who is somewhat unfamiliar with the language of ...
1
vote
0answers
97 views
Shortest s-t Path with a covering constraint
Instance: an undirected graph $G=(V,E)$ with edge-weights $w:E\to{\mathbb{R}}$;
a source $s\in V$ and a sink $t\in V$;
a ground set $X=\{x_1, ..., x_k\}$, and for every $v\in V$ a corresponding ...
5
votes
1answer
251 views
The asymptotic behavior of a recurrence related to stable matchings
I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows:
$$a_1 = 1, a_2 = 2$$
$$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$
Apparently, Knuth was able to prove that ...
2
votes
0answers
139 views
Sensitivity and Low-Degree Approximation under Non-Uniform Distribution
I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
2
votes
1answer
87 views
Placing color boxes on a colored image such that color consistency is maximized
I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem.
Given an image with black background that contains blobs whose ...
0
votes
0answers
71 views
Lower bound for permutation generator
I'm interested in a problem akin to combinatorial circuits, but in terms of complexity. Apologies for missing the correct terminology, I'll appreciate any corrections.
Given $n$ inputs numbered $1 ......
1
vote
1answer
92 views
How to play the following game? (placing balls into bins)
Let $n,\ell\in\mathbb N$ for some $n\gg \ell\gg 1$.
The goal is to pick two sequences of numbers, $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_\ell$ such that $$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\...