Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
19
votes
3answers
11k views

Counting the Number of Simple Paths in Undirected Graph

How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths. Recall that a simple path is a path with no ...
23
votes
8answers
3k views

graphs from real-life problems

Where can I find graphs relevant to real-life problems? Two repositories I know of are: University of Florida's Sparse Matrix Collection Bodlaender's TreewidthLib
37
votes
6answers
3k views

Grid $k$-coloring without monochromatic rectangles

Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known. Anyone feel up to trying 5-colorings? ;...
39
votes
3answers
9k views

Is optimally solving the n×n×n Rubik's Cube NP-hard?

Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ...
28
votes
4answers
1k views

Maximal classes for which largest independent set can be found in polynomial time?

The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile ...
28
votes
5answers
4k views

Counting words accepted by a regular grammar

Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of ...
8
votes
2answers
2k views

Faster pseudo-polynomial time algorithms for PARTITION

I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or ...
19
votes
1answer
2k views

What is the number of languages accepted by a DFA of size $n$?

The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this: Define a DFA as $(Q,\Sigma,\delta,...
14
votes
2answers
3k views

Integer programming with a fixed number of variables

The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of ...
2
votes
1answer
547 views

techniques or examples of analyzing a series of graphs

Let there be a sequence of graphs $G_1, G_2, G_3, ...$ constructed using some particular approach or algorithm. in this particular case $G_n$ is constructed by modifying $G_{n-1}$ in some "...
43
votes
12answers
4k views

Applications of representation theory of the symmetric group

Inspired by this question and in particular the final paragraph of Or's answer, I have the following question: Do you know of any applications of the representation theory of the symmetric group in ...
19
votes
3answers
2k views

Shortest Equivalent CNF Formula

Let $F_1$ be a satisfiable CNF Formula with $n$ variables and $m$ clauses. Let $S_{F_1}$ be the solution space of $F_1$. Consider the problem of determining, given $F_1$, another CNF Formula $F_2$ ...
30
votes
4answers
3k views

Complexity of applying a permutation in-place

To my surprise, I was not able to find papers about this - probably searched the wrong keywords. So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation. How do ...
25
votes
1answer
1k views

An edge partitioning problem on cubic graphs

Has the complexity of the following problem been studied? Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$ Question: is there a partition of $E$ into $|E|/3$ parts of size $...
17
votes
2answers
1k views

Cover Time of Directed Graphs

Given a random walk on a graph the cover time is the first time (expected number of steps) that every vertex has been hit (covered) by the walk. For connected undirected graphs, the cover time is ...
16
votes
2answers
3k views

Minimum number of transpositions to sort a list

In trying to devise my own sorting algorithm, I'm looking for the optimal benchmark to which I can compare it. For an unsorted ordering of elements A and a sorted ordering B, what is an efficient way ...
29
votes
2answers
2k views

Can you identify the sum of two permutations in polynomial time?

There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question: Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
9
votes
3answers
2k views

What kind of mathematical background is needed for graph theory?

It is going to be the first time for me to learn graph theory. What kind of mathematical background do I need to prepare master theses about this subject in following years? Which subjects should be ...
12
votes
2answers
2k views

Cover a Concave Polygon with a minimum number of rectangles

I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle. I thought about ...
27
votes
2answers
1k views

Maximal/maximum independent sets

Is there something known about the class of graphs with the property that all maximal independent sets have the same cardinality and are therefore maximum ISs? For example, take a set of points in ...
11
votes
4answers
708 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Crossposted from MO. Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there NP-hard graph problems that ...
9
votes
2answers
984 views

Generating interesting combinatorial optimization problems

I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...
14
votes
2answers
2k views

Application of Ramsey Numbers

The definition of Ramsey numbers is the following: Let $R(a,b)$ be a positive number such that every graph of order at least $R(a,b)$ contains either a clique on $a$ vertices or a stable set on $b$ ...
8
votes
1answer
591 views

An interesting variant of maximum matching problem

Given a graph $G(V,E)$, the classic maximum matching problem is choosing the maximum subset of edges $M$ s.t., for each edge $(u,v) \in M$, $d(u)=d(v)=1$. Has anybody studied the following variant? ...
6
votes
2answers
784 views

Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function. The Fourier expansion of $f$ is $$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$ where $\widehat{f}(S)$ are real numbers ...
3
votes
1answer
338 views

Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?

Sorry for not-precise question. :-( There are several papers concerning exact counting (maximum) independent sets in general graphs. Actually, they concerns counting of solutions of 2SAT. The best of ...
55
votes
13answers
4k views

Information Theory used to prove neat combinatorial statements?

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ? Some examples I can think of are related to lower bounds for locally decodable ...
64
votes
5answers
6k views

The origin of the notion of treewidth

My question today is (as usual) a bit silly; but I would request you to kindly consider it. I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
44
votes
10answers
4k views

Kolmogorov complexity applications in computational complexity

Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...
39
votes
13answers
3k views

Using error-correcting codes in theory

What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of ...
29
votes
2answers
920 views

Polynomial method for complexity results

Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee ...
24
votes
6answers
2k views

Graph families which have polynomial time algorithms for computing the chromatic number

Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings. ...
52
votes
1answer
1k views

A combinatorial version for the polynomial Hirsch conjecture

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ . Suppose that (*) For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
18
votes
11answers
4k views

Are there any applications of techniques in real analysis to theoretical computer science?

I have looked far and wide for such applications and have mostly turned up short. I can find plenty of applications of topology and similar structures on countable (or uncountable) sets, but rarely do ...
23
votes
4answers
2k views

Social choice, arrow's theorem and open problems ?

Last few months I started to lecture myself on social choice, arrow's theorem and related results. After reading about the seminal results, I asked myself about what happens with partial order ...
6
votes
3answers
2k views

Mathematical background needed for pursuing a PhD in TCS [duplicate]

Possible Duplicate: What kind of mathematical background is needed for complexity theory? I'm a final year undergrad and I'm looking to pursue a PhD in theoretical computer science in the long ...
10
votes
4answers
703 views

What are the root difficulties in going from graphs to hypergraphs?

There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking. Why do you think problems ...
25
votes
2answers
823 views

Computational complexity of counting induced subgraphs which admit perfect matchings

Given an undirected and unweighted graph $G=(V,E)$ and an even integer $k$, what is the computational complexity of counting sets of vertices $S\subseteq V$ such that $|S|=k$ and the subgraph of $G$ ...
21
votes
4answers
3k views

What are infinite graphs good for?

I have just read on the German Wikipedia that an infinite graph is a graph with an infinite number of nodes or an infinite number of edges. I only know applications and algorithms for finite graphs. ...
12
votes
1answer
2k views

Efficient algorithm for existence of permutation with differences sequence?

This question is motivated by this post, Can you identify the sum of two permutations in polynomial time? , and my interest in computational properties of permutations. A differences sequence $a_1, ...
25
votes
2answers
2k views

Is it decidable to determine if a given shape can tile the plane?

I know that it is undecidable to determine if a set of tiles can tile the plane, a result of Berger using Wang tiles. My question is whether it is also known to be undecidable to determine if a single ...
24
votes
1answer
579 views

Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant literature,...
17
votes
3answers
1k views

Properties of Random Directed Graphs with Fixed Out-Degree

I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r. ...
16
votes
1answer
650 views

Why are perfect graphs called perfect?

Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is ...
13
votes
2answers
376 views

H-free partition

This is a question inspired by the H-free cut problem. Given a graph, a partition of its vertex set $V$ into $r$ parts $V_1, V_2, \ldots, V_r$ is $H$-free if $G[V_i]$ does not induce a copy of $H$ for ...
12
votes
3answers
901 views

Edge-partitioning cubic graphs into claws and paths

Again an edge-partitioning problem whose complexity I'm curious about, motivated by a previous question of mine. Input: a cubic graph $G=(V,E)$ Question: is there a partition of $E$ into $E_1, E_2, \...
19
votes
1answer
6k views

Partition a graph into node-disjoint cycles

Related problem: Veblen’s Theorem states that "A graph admits a cycle decomposition if and only if it is even". The cycles are edge disjoint, but not necessarily node disjoint. Put another way, "The ...
15
votes
1answer
500 views

Decomposing graphs of genus one

Planar graphs are $K_{3,3}$-free. Such graphs can be decomposed into tri-connected components, which are known to be either planar or $K_5$ components. Is there such a "nice" decomposition of ...
13
votes
1answer
413 views

Ramsey's theorem for collections of sets

While exploring different techniques of proving lower bounds for distributed algorithms, it occurred to me that the following variant of Ramsey's theorem might have applications – if it happens to be ...
12
votes
1answer
367 views

Do "outer-bounded-genus" graphs have constant treewidth?

Let $k\in\mathbb{N}$ and denote by $G_k$ the set of all graphs that can be embedded on a surface of genus $k$ such that all vertices are situated on the outer face. For instance, $G_0$ is the set of ...