Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
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 ...
user avatar
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{...
user avatar
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 ...
user avatar
  • 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=...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
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{...
user avatar
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)...
user avatar
  • 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$. ...
user avatar
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 $...
user avatar
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 $\...
user avatar
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 ...
user avatar
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 ...
user avatar
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\...
user avatar
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 =...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$, ...
user avatar
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\...
user avatar
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 ...
user avatar
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?
user avatar
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)$...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
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 ...
user avatar
-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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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....
user avatar

1
2 3 4 5
13