Questions tagged [co.combinatorics]
Questions related to combinatorics and discrete mathematical structures
642
questions
1
vote
0
answers
47
views
The tree augmentation problem, but with hyperlinks
In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...
- 557
2
votes
0
answers
44
views
Sorting multiple columns of a matrix
Let $A \in \mathbb{R}^{n \times k}$ be a matrix where each column contains all of the numbers from $\{1,\dots,n\}$ in some arbitrary order. For example, if $n=3, k=2$, we could have
$$ A =
\begin{...
- 179
2
votes
2
answers
148
views
Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$
Given: a (long binary) string $\ell$, and a set of (short) strings, $s_1, s_2, ...$ . Can $\ell$ be written as concatenation of the short strings?
I am looking for references on: the name of the ...
- 121
3
votes
1
answer
137
views
Maximal uniquely decodable codes
This question is about the Kraft-McMillan inequality:
If $w_1,\ldots,w_n$ are words of lengths $l_1,\ldots,l_n$ from an alphabet with $r$ letters, which form a uniquely decodable code, then
$$ \sum_{i=...
- 33
0
votes
0
answers
30
views
Multi-dimensional 0-1 Knapsack problem with a high number of dimensions
I would like to solve a multi-dimensional 0-1 Knapsack problem, by looking for approximation algorithms with constant approximation ratio if possible. Here the particularity is that the number of ...
- 101
0
votes
0
answers
28
views
A question regarding the proof of Lévy–Steinitz theorem
I have asked this question in math.stackexchange.com four days ago. I did not get any feedback, so I am asking it here.
I am reading the proof of Lévy–Steinitz theorem from ON THE POWER OF LINEAR ...
- 267
2
votes
1
answer
171
views
Maximize a special monotone submodular function - is it easier?
I am looking for a way to optimize the function $f$, defined below.
First, fix some positive integer $k$ and let $c_1$ and $c_2$ be non-negative vectors in $\mathbb{R}^n$. Let $g$ be an increasing ...
- 557
1
vote
0
answers
56
views
On Negami's planar cover cojecture
For this question, let us consider only simple, finite, undirected graphs.
A homomorphism $\psi$ from a graph a $G$ to a graph $H$, $\psi\colon V(G)\to V(H)$, is a Locally Bijective Homomorphism from $...
- 1,603
0
votes
1
answer
88
views
On structure of graphs with average degree equal to maximum average degree
For a simple graph $G$, the $\text{average-degree}(G)=|E(G)|/|V(G)|$ and
the maximum average degree $\text{mad}(G)=\max\{\text{average-degree}(H)\colon H \text{ is a subgraph of } G\}$.
If $\text{...
- 1,603
2
votes
0
answers
66
views
Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?
Given a graph $G=(V,E)$, costs $c \in \mathbb{R}^E$ the TSP problem is to compute a min cost tour of the graph. The LP is
min $ c^tx $
$x(\delta(S)) \geq 2 \ \ \ \ \forall S \subset V $
$x(\delta(v)...
- 217
2
votes
0
answers
61
views
Can this relaxed subset-sum problem be solved with a smaller dynamic program? [closed]
Cross-post from CS.SE
In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$.
...
- 1,826
3
votes
0
answers
44
views
Does high connectivity of line graph of $G$ imply high (cyclic) connectivity of $G$?
All graph considered here are finite, simple and undirected.
We know that a graph $G$ is $k$-edge connected if and only if its line graph is $k$-connected (where $k\in\mathbb{N}$). In particular, if $...
- 1,603
3
votes
1
answer
102
views
On cubic planar graphs with face boundaries of length divisible by 4
All graphs considered here are finite, simple and undirected.
Let $\mathscr{G}$ denote the class of cubic plane graphs for which all face boundaries are of length divisible by four. The 3-cube $Q_3$ ...
- 1,603
1
vote
0
answers
28
views
Cycle decompositions of locally linear 4-regular graphs
(Preface)
We consider only finite, simple, undirected graphs here. An orientation of a graph $G$ is obtained by assigning some direction to each edge of $G$.
(Question starts)
A graph is locally ...
- 1,603
2
votes
0
answers
52
views
Bin packing with non-additive load functions
I am looking for information on the bin packing problem, where the load of each bin is not the sum of items in the bin, but some other monotone set function. For example, suppose each item $i$ has ...
- 1,826
1
vote
0
answers
33
views
Is arrangement-type graph on cyclic $k$-permutations of $n$ already studied?
The arrangement graph $A_{n,k}$ is the graph whose vertices are $k$-permutations of an $n$-vertex set $X$ (say, $X=\mathbb{Z}_n$) and two $k$-permutations are adjacent if they differ in exactly one ...
- 1,603
6
votes
1
answer
252
views
How can we compute the VC dimension of a finite class of sets?
Let $F$ be a class of subsets of a finite set $X$ of cardinality $n$. What is the complexity of computing the VC dimension of $F$? Can we do better than looping through every subset of $X$ and ...
- 237
1
vote
0
answers
45
views
Approximate solution for maximum coverage problem with choice constraint
Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\...
9
votes
1
answer
253
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 ...
- 103
0
votes
0
answers
22
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 ...
- 557
5
votes
2
answers
260
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\...
- 103
1
vote
1
answer
101
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 =...
- 557
0
votes
1
answer
160
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 ...
- 557
7
votes
1
answer
287
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 ...
- 73
1
vote
1
answer
96
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 ...
- 557
2
votes
1
answer
125
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
1
answer
153
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 ...
- 407
3
votes
1
answer
348
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
1
answer
74
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\...
- 151
4
votes
1
answer
184
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 ...
- 557
3
votes
0
answers
89
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?
- 31.6k
0
votes
0
answers
73
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)$...
- 557
5
votes
0
answers
170
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 ...
- 557
3
votes
2
answers
175
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 ...
- 117
2
votes
1
answer
39
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 ...
- 23
-2
votes
1
answer
110
views
Subset sum for lists [closed]
Given a target list
a = [2,4,1,4]`
and a list of lists
...
7
votes
1
answer
172
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 ...
- 285
2
votes
1
answer
90
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 ...
- 803
0
votes
0
answers
96
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. ...
- 1
0
votes
1
answer
160
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 ...
- 6,615
2
votes
0
answers
106
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 ...
- 9,378
2
votes
0
answers
91
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 ...
- 21
2
votes
1
answer
155
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.
- 557
1
vote
2
answers
109
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 ...
- 21
-4
votes
1
answer
121
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 ...
- 101
1
vote
0
answers
119
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-...
- 387
1
vote
1
answer
87
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 ...
- 241
2
votes
1
answer
106
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 ...
- 57
11
votes
3
answers
638
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
...
- 470
2
votes
2
answers
129
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....
- 455